#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
  int n;
  cin >> n;
  i64 c;
  cin >> c;
  vector<i64> a(n), b(n), d(n), ra(n), rb(n);
  i64 ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    ans += abs(a[i] - b[i]);
    d[i] = b[i];
  }
  ans /= 2;
  sort(d.begin(), d.end());
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
    b[i] = lower_bound(d.begin(), d.end(), b[i]) - d.begin();
    ra[a[i]] = i;
    rb[b[i]] = i;
  }
  vector<pair<int, int>> op;
  auto work = [&](int u, int v) {
    ans += c;
    ra[a[u]] = v;
    ra[a[v]] = u;
    swap(a[u], a[v]);
    op.push_back({u, v});
  };
  for (int cur = 0; cur < n; cur++) {
    int u = rb[cur];
    while (b[u] != a[u]) {
      auto ok = [&](int v) {
        return a[u] <= b[v] && a[u] > a[v];
      };
      int v1 = u, v2 = u;
      while (1) {
        v1 = rb[a[v1]];
        v2 = ra[b[v2]];
        if (ok(v1)) {
          work(u, v1);
          break;
        }
        if (ok(v2)) {
          work(u, v2);
          break;
        }
      }
    }
  }
  cout << ans << " " << op.size() << "\n";
  for (auto &[x, y] : op) {
    cout << x + 1 << " " << y + 1 << "\n";
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}