#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=0;
		if((m+1)/2>=n)
		{
			maxn=num;
		}
		for(int i=1;i<=n;i++)
		{
			sum[i]=sum[i-1]+w[i].z;
		}
		for(int x=2;x<=n;x++)
		{
//			if(x==1)
//			{
//				continue;
//			}
			if(( (m-x)/2 )<n-x)
			{
				continue;
			}
			maxn=max(maxn,num+sum[x]);
		}
		cout<<maxn<<endl;
	}
}