#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int p[MAXN];
array <int,3> a[MAXN];
bool vis[MAXN];
void solve() {
	int n,cnt=0; long long ans=0,C;
	scanf("%d%lld",&n,&C);
	for(int i=1;i<=n;++i) {
		scanf("%d%d",&a[i][1],&a[i][0]);
		ans+=abs(a[i][0]-a[i][1]),a[i][2]=i;
	}
	sort(a+1,a+n+1),ans/=2;
	for(int i=1;i<=n;++i) p[i]=lower_bound(a+1,a+n+1,array<int,3>{a[i][1],0,0})-a;
	vector <array<int,2>> wys;
	auto opr=[&](int x,int y) { swap(p[x],p[y]),wys.push_back({a[x][2],a[y][2]}); };
	fill(vis+1,vis+n+1,0);
	for(int i=1;i<=n;++i) if(!vis[i]) {
		++cnt;
		int x=i;
		for(int j=i;!vis[j];j=p[j]) vis[j]=true,x=max(x,j);
		int u=x; vector <int> q;
		while(p[u]!=x) {
			if(p[u]>u) {
				q.erase(upper_bound(q.begin(),q.end(),p[u],greater<int>()),q.end());
				int v=q.back();
				opr(v,u);
				while(p[u]!=u) opr(u,p[u]);
				u=p[v];
			} else q.push_back(u),u=p[u];
		}
		while(p[u]!=u) opr(u,p[u]);
	}
	printf("%lld %d\n",ans+1ll*C*(n-cnt),n-cnt);
	for(auto z:wys) printf("%d %d\n",z[0],z[1]);
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}