#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cmath>
#include <unordered_map>
#include <map>
#include <deque>
#include <cstdio>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int maxD = 1e5 + 2;
ll prefv[maxD], sel[maxD];
pair<int, int> xv[maxD];
int main()
{
int t;
cin >> t;
for(int i = 1; i <= t; ++i)
{
int n, R, k;
ll ans = 0;
int mini = 1e9;
cin >> n >> R >> k;
for(int j = 0; j < n; ++j)
{
int x, v;
cin >> x >> v;
xv[j] = make_pair(x, v);
mini = min(x, mini);
prefv[j] = 0;
sel[j] = -1;
}
sort(xv, xv + n);
prefv[0] = xv[0].second;
for(int j = 1; j < n; ++j) prefv[j] += prefv[j - 1] + xv[j].second;
for(int j = 0; j < k; ++j)
{
int l, r, curl;
ll best;
pair<int, int> bestcur;
l = r = best = curl = 0;
for(int m = 0; m < n; ++m)
{
if( sel[m] != -1 )
{
m = sel[m];
curl = m;
continue;
}
l = curl;
r = m;
if( xv[m].first - mini <= R * 2 )
{
if( prefv[m] >= best ) {
best = prefv[m];
bestcur = make_pair(m, 0);
continue;
}
}
while(l + 1 < r)
{
int mid = (l + r) >> 1;
if( xv[m].first - xv[mid + 1].first <= R * 2 ) r = mid;
else l = mid;
}
if( xv[m].first - xv[l + 1].first <= R * 2 ) r = l;
if( prefv[m] - prefv[r] >= best )
{
best = prefv[m] - prefv[r];
bestcur = make_pair(m, r + 1);
}
}
ans += best;
if( best )
sel[bestcur.second] = bestcur.first;
}
cout << "Case " << i << ": " << ans << '\n';
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx1bm9yZGVyZWRfbWFwPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8ZGVxdWU+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxzdGRpby5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBsb25nIGxvbmcgbGw7Cgljb25zdCBpbnQgbWF4RCA9IDFlNSArIDI7CgkgbGwgcHJlZnZbbWF4RF0sIHNlbFttYXhEXTsKCSBwYWlyPGludCwgaW50PiB4dlttYXhEXTsKCmludCBtYWluKCkKewoJaW50IHQ7CgljaW4gPj4gdDsKCWZvcihpbnQgaSA9IDE7IGkgPD0gdDsgKytpKQoJewoJCWludCBuLCBSLCBrOwoJCWxsIGFucyA9IDA7CgkJaW50IG1pbmkgPSAxZTk7CgkJY2luID4+IG4gPj4gUiA+PiBrOwoJCWZvcihpbnQgaiA9IDA7IGogPCBuOyArK2opIAoJCXsKCQkJaW50IHgsIHY7CgkJCWNpbiA+PiB4ID4+IHY7CgkJCXh2W2pdID0gbWFrZV9wYWlyKHgsIHYpOwoJCQltaW5pID0gbWluKHgsIG1pbmkpOwoJCQlwcmVmdltqXSA9IDA7CgkJCXNlbFtqXSA9IC0xOwoJCX0KCQlzb3J0KHh2LCB4diArIG4pOwoJCXByZWZ2WzBdID0geHZbMF0uc2Vjb25kOwoJCWZvcihpbnQgaiA9IDE7IGogPCBuOyArK2opIHByZWZ2W2pdICs9IHByZWZ2W2ogLSAxXSArIHh2W2pdLnNlY29uZDsKCQlmb3IoaW50IGogPSAwOyBqIDwgazsgKytqKQoJCXsKCQkJaW50IGwsIHIsIGN1cmw7CgkJCWxsIGJlc3Q7CgkJCXBhaXI8aW50LCBpbnQ+IGJlc3RjdXI7CgkJCWwgPSByID0gYmVzdCA9IGN1cmwgPSAwOwoJCQlmb3IoaW50IG0gPSAwOyBtIDwgbjsgKyttKQoJCQl7CgkJCQlpZiggc2VsW21dICE9IC0xICkgCgkJCQl7CgkJCQkJbSA9IHNlbFttXTsKCQkJCQljdXJsID0gbTsKCQkJCQljb250aW51ZTsKCQkJCX0KCgkJCQlsID0gY3VybDsKCQkJCXIgPSBtOwoJCQkJaWYoIHh2W21dLmZpcnN0IC0gbWluaSA8PSBSICogMiApIAoJCQkJewoJCQkJCWlmKCBwcmVmdlttXSA+PSBiZXN0ICkgewoJCQkJCQliZXN0ID0gcHJlZnZbbV07CgkJCQkJCWJlc3RjdXIgPSBtYWtlX3BhaXIobSwgMCk7CgkJCQkJCWNvbnRpbnVlOwoJCQkJCX0KCQkJCX0KCgkJCQl3aGlsZShsICsgMSA8IHIpCgkJCQl7CgkJCQkJaW50IG1pZCA9IChsICsgcikgPj4gMTsKCQkJCQlpZiggeHZbbV0uZmlyc3QgLSB4dlttaWQgKyAxXS5maXJzdCA8PSBSICogMiApIHIgPSBtaWQ7CgkJCQkJZWxzZSBsID0gbWlkOwoJCQkJfQoJCQkJCgkJCQlpZiggeHZbbV0uZmlyc3QgLSB4dltsICsgMV0uZmlyc3QgPD0gUiAqIDIgKSByID0gbDsKCgkJCQlpZiggcHJlZnZbbV0gLSBwcmVmdltyXSA+PSBiZXN0ICkKCQkJCXsKCQkJCQkJYmVzdCA9IHByZWZ2W21dIC0gcHJlZnZbcl07CgkJCQkJCWJlc3RjdXIgPSBtYWtlX3BhaXIobSwgciArIDEpOwoJCQkJfQoJCQl9CgoJCQlhbnMgKz0gYmVzdDsKCQkJaWYoIGJlc3QgKQoJCQkJc2VsW2Jlc3RjdXIuc2Vjb25kXSA9IGJlc3RjdXIuZmlyc3Q7CgkJfQoJCWNvdXQgPDwgIkNhc2UgIiA8PCBpIDw8ICI6ICIgPDwgYW5zIDw8ICdcbic7Cgl9CgoJcmV0dXJuIDA7Cn0=