#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(a) (int)(a).size()
#define fori(i,b,e) for(int i = (b); i < (e); i++)
#define forn(i,n) fori(i,0,n)

typedef long long int64;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;

int getInt() { int x; scanf("%d", &x); return x;}

const int maxn = 150100;
int v[maxn], c[maxn], d[maxn];
bool was[maxn];

void solve() {
	int n = getInt(), k = getInt();
	fori(i,0,n) {
		v[i] = getInt();
		c[i] = getInt();
		d[i] = v[i] - c[i];
	}
	int l = 0, r = 1e6 + 5;
	while (r - l > 1) {
		int ans = (l + r) >> 1;
		bool good = true;
		vector<pii> curs;
		fori(ttt,0,k+1) {
			if (!good)
				break;
			int mini = -1;
			fori(i,0,n) {
				if (!was[i] && (mini == -1 || c[i] < c[mini])) {
         			int lim = sz(curs);
         			fori(i,0,sz(curs)) {
         				if (curs[i].second > d[mini]) {
         					lim = i;
         					break;
         				}
         			}
	       			if (c[i] + (lim == 0 ? 0 : curs[lim-1].first) <= d[i] - ans) {
						bool locGood = true;
						fori(j,lim,sz(curs)) {
							if (curs[j].first + c[i] > curs[j].second - ans) {
								locGood = false;
								break;
							}
						}
					 	if (locGood)
							mini = i;
         			}
				}
			}
			if (mini == -1) {
				good = false;
				break;
			}
			was[mini] = 1;
			int lim = sz(curs);
			fori(i,0,sz(curs)) {
				if (curs[i].second > d[mini]) {
					lim = i;
					break;
				}
			}
			curs.insert(curs.begin() + lim, mp(c[mini] + (lim == 0 ? 0 : curs[lim-1].first), d[mini]));
			fori(i,lim+1,sz(curs)) {
				curs[i].first += c[mini];
			}
		}
		fori(i,0,n)
			was[i] = false;
		if (good) {
			l = ans;
		} else {
			r = ans;
		}
	}
	printf("%d\n", l);
}

int main() {
#ifdef DEBUG
	freopen("in.txt", "rt", stdin);
	freopen("out.txt", "wt", stdout);
#endif
	int n = getInt();
	fori(i,0,n)
		solve();
	return 0;
}