/*  This Code is Submitted by wywcgs for Problem 1218 on 2006-08-17 at 00:05:33 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 102400;
const int INF = 1 << 30;

class Event {
public:
	int t, x, pos, neg;
	void make() { scanf("%d %d", &t, &x); pos = t-x; neg = t+x; }
	bool operator <(const Event& e) const { return neg < e.neg; }
};

int n, m;
Event e[N];

bool occur(int);

int main()
{
	int T;

	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		scanf("%d %d", &n, &m);
		for(int i = 0; i < n; i++) e[i].make();
		sort(e, e+n);
		int l = INF, h = INF;
		for(int i = 0; i < n; i++)
			{ l <?= e[i].pos; h <?= e[i].t; }
		l = (l+e[0].neg)/2;
		while(l != h) {
			int mid = (l+h+1)/2;
			if(occur(mid)) l = mid;
			else h = mid-1;
		}
		printf("Case %d: %d\n", t, h);
	}
	
	return 0;
}

bool occur(int low)
{
	int used = 0; low *= 2;
	for(int i = 0, j = 0; i < n; i = j) {
		used++;
		if(used > m) return false;
		for(; j < n && e[i].neg+e[j].pos >= low; j++);
	}
	return true;
}