#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=5e5+5;
int t,n,m;
struct node{
	ll p,v;
}z[N];
bool cmp(node a,node b){
	if(a.v==b.v)return a.p<b.p;
	return a.v>b.v;
}
priority_queue<int>q;
ll maxx[N];
signed main(){
//	freopen("test.in","r",stdin);
	read(t);
	while(t--){
		ll ans=0;
		ll tmp=0,tmp2=0;
		read(n);read(m);
		ll wtf=0;
		for(int i=1;i<=n;i++){
			read(z[i].v);read(z[i].p);
//			wtf+=max(z[i].v-z[i].p,(ll)0);
		}
//		cout<<wtf<<endl;
		sort(z+1,z+1+n,cmp);
		if(m>n){
			puts("0");continue;
		}
		for(int i=1;i<m;i++){
			q.push(z[i].p);tmp+=z[i].p;
		}
		maxx[n+1]=z[n].v-z[n].p;
		for(int i=n;i>=m;i--){
			tmp2+=max((ll)0,z[i].v-z[i].p);
			maxx[i]=max(maxx[i+1],z[i].v-z[i].p);
		} 
//		if(m==1){
//			cout<<tmp2<<endl;continue;
//		}
		ans=max(ans,tmp2+m-1-tmp);
		for(int i=m;i<=n;i++){
			if(!q.empty()&&q.top()>z[i].p){
				tmp-=q.top();q.pop();q.push(z[i].p);tmp+=z[i].p;
			}
			if(z[i].v>z[i].p)tmp2-=z[i].v-z[i].p;
			ans=max(ans,tmp2+m-1-tmp);
//			cout<<ans<<endl;
		}
		printf("%lld\n",ans);
		while(!q.empty())q.pop();
	}
	
	
	return 0;
}