#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int t,n,m;
int sum[N];
struct node
{
	int a,b,z;
}w[N];
bool cmp(node x,node y)
{
	return x.z>y.z;
}
signed main()
{
	cin>>t;
	while(t--)
	{
		int num=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>w[i].a>>w[i].b;
			num+=w[i].b;
			w[i].z=w[i].a-w[i].b;
		}
		sort(w+1,w+n+1,cmp);
		int maxn=num;
		//cout<<"@@@"<<endl;
		for(int i=1;i<=n;i++)
		{
		//	cout<<w[i].z<<"  ";
			sum[i]=sum[i-1]+w[i].z;
		}
		for(int x=2;x<=n;x++)
		{
			if(( (m-x)/2 )<n-x)
			{
				continue;
			}
			maxn=max(maxn,num+sum[x]);
		//	cout<<666<<endl;
		}
		cout<<maxn<<endl;
	}
}