#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 500005

int n,m,a[MAXN],b[MAXN],sec[MAXN],f[MAXN];

inline bool cmp( int x , int y ){ return a[x] - b[x] > a[y] - b[y]; }

inline void solve(){
	scanf("%lld%lld",&n,&m);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld%lld",&a[i],&b[i]);
	for( int i = 1 ; i <= n ; i ++ ) sec[i] = i;
	sort( sec + 1 , sec + n + 1 , cmp );
	for( int i = 0 ; i <= n ; i ++ ) f[i] = 0;
	for( int i = 1 ; i <= n ; i ++ ) f[0] += b[i];
	for( int i = 1 ; i <= n ; i ++ ) f[i] = f[i - 1] + a[sec[i]] - b[sec[i]];
	int Ans = 0;
	for( int j = 0 ; j <= n ; j ++ ){
		if( ( j == 0 && 2 * n - 1 > m ) || j == 1 || ( j != 0 && 2 * ( n - j ) + j > m ) ) continue;
		Ans = max( Ans , f[j] );
	}
	printf("%lld\n",Ans);
}

signed main(){
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}