#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int T;
ll n,m;

inline ll read() {
	ll c=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		c=c*10+ch-'0';
		ch=getchar();
	}
	return c*f;
}

struct Node {
	ll a,b;
	bool operator<(const Node&W)const {
		return b-a>W.b-W.a;
	}
} node[N];

void init() {
	n=read(),m=read();

	ll res = 0;
	ll mmax;
	for(int i=1; i<=n; i++) {
		node[i].a=read(),node[i].b=read();
		res+=node[i].a;
	}
	mmax = res;
	sort(node+1,node+1+n);



	ll len = m-n;
	for(int i=1; i<=n-1; i++) {
		if(len<1)break;

		ll tem = node[i].b;

		len+=1;
		len -= 2;
		res -= node[i].a;
		res += node[i].b;
		if(i==n-1) {
			res -= node[n].a;
			res += node[n].b;

		}
		mmax = max(res,mmax);

	}




	cout<<mmax<<endl;

}

int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	T=read();
	while(T--) {
		init();
	}
	return 0;
}