#include <cstdio>
#include <algorithm>
#define int long long

using namespace std;

const int N = 500000;
int n, m;

struct Node
{
	int a, b;
	bool operator < (const Node &x) const
	{
		int f1 = (a >= b), f2 = (x.a >= x.b);
		if(f1 != f2)
		{
			return f1 < f2;
		}
		return a - b < x.a - x.b;
	}
}node[N + 5];

void init()
{
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld %lld", &node[i].a, &node[i].b);
	}
}

void solve()
{
	sort(node + 1, node + n + 1);
	int p;
	for(p = 1; p <= n; p++)
	{
		if(node[p].a >= node[p].b)
		{
			break;
		}
	}
	int ans = 0;
	if(p == 1)
	{
		if(n == 1)
		{
			ans = node[1].b;
		}
		else
		{
			for(int i = 1; i <= n; i++)
			{
				ans += node[i].a;
			}
		}
		printf("%lld\n", ans);
		return;
	}
	if(p >= n)
	{
		if(n * 2 - 1 <= m)
		{
			for(int i = 1; i <= n; i++)
			{
				ans += node[i].b;
			}			
			if(p == n && node[n - 1].a - node[n - 1].b + node[n].a - node[n].b > 0)
			{
				ans += node[n - 1].a - node[n - 1].b + node[n].a - node[n].b;
			}
		}
		else
		{
			int x = n * 2 - m;
			for(int i = 1; i <= n - x; i++)
			{
				ans += node[i].b;
			}
			for(int i = n - x + 1; i <= n; i++)
			{
				ans += node[i].a;
			}
		}
		printf("%lld\n", ans);
		return;
	}
	if((p - 1) * 2 + (n - p + 1) <= m)
	{
		for(int i = 1; i < p; i++)
		{
			ans += node[i].b;
		}
		for(int i = p; i <= n; i++)
		{
			ans += node[i].a;
		}
	}
	else
	{
		int x = n * 2 - m;
		for(int i = 1; i <= n - x; i++)
		{
			ans += node[i].b;
		}
		for(int i = n - x + 1; i <= n; i++)
		{
			ans += node[i].a;
		}
	}
	printf("%lld\n", ans);
}

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