#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair 
using namespace std;
const int N=1000005;
typedef long long ll;
struct node{
	int x,y,id;
	node(int _x=0,int _y=0,int _id=0):x(_x),y(_y),id(_id){}
	bool operator<(const node &rhs)const{
		return y<rhs.y;
	}
}a[N];
vector<pii> ans;
int T,n,C,p[N],pos[N];ll res;
void upd(int x,int y)
{
	ans.push_back(mp(a[x].id,a[y].id));
	swap(p[x],p[y]);pos[p[x]]=x;pos[p[y]]=y;
	res+=abs(a[x].x-a[y].x)+C;swap(a[x].x,a[y].x);
}
int main()
{
	scanf("%d",&T);
	while(T--)	
	{
		scanf("%d%d",&n,&C);ans.clear();res=0;
		for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
		sort(a+1,a+n+1);for(int i=1;i<=n;++i)p[i]=lower_bound(a+1,a+n+1,node(0,a[i].x,0))-a,pos[p[i]]=i;
		for(int i=1;i<=n;++i)
		{
			while(p[i]!=i)
			{
				int l=i,r=i;
				while(1)
				{
					l=p[l];if(l>=p[i]&&p[i]>p[l]){upd(l,i);break;}
					r=pos[r];if(r>=p[i]&&p[i]>p[r]){upd(r,i);break;}
				}
			}
		}
		printf("%lld %d\n",res,(int)ans.size());
		for(auto p:ans)printf("%d %d\n",p.first,p.second);
	}
	return 0;
}