//84104971101048411497 - Can you guess what does this mean?
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 1005
#define oo 1000000000000000007LL
#define sz(a) (int)a.size()
const double PI = acos(-1.0);
double fRand(double fMin, double fMax)
{
double f = (double)rand() / RAND_MAX;
return fMin + f * (fMax - fMin);
}
template <class T>
T min(T a, T b, T c) {
return min(a, min(b, c));
}
template <class T>
T max(T a, T b, T c) {
return max(a, max(b, c));
}
int nTest, R, B, C, M[maxN], S[maxN], P[maxN];
bool Check(ll x) {
vector<int> b;
fto(i, 1, C)
if (x >= P[i]) b.pb(min(1LL*M[i], (x-P[i])/S[i]));
sort(b.begin(), b.end());
reverse(b.begin(), b.end());
ll sum = 0;
fto(i, 0, min(sz(b), R)-1) sum += b[i];
return sum >= B;
}
int main () {
scanf("%d", &nTest);
fto(iTest, 1, nTest) {
printf("Case #%d: ", iTest);
scanf("%d%d%d", &R, &B, &C);
fto(i, 1, C) scanf("%d%d%d", &M[i], &S[i], &P[i]);
ll lo = 1, hi = oo, res = 0;
while (lo <= hi) {
ll mid = (lo+hi)/2;
if (Check(mid)) {
res = mid;
hi = mid-1;
} else lo = mid+1;
}
printf("%lld\n", res);
}
return 0;
}
Ly84NDEwNDk3MTEwMTA0ODQxMTQ5NyAtIENhbiB5b3UgZ3Vlc3Mgd2hhdCBkb2VzIHRoaXMgbWVhbj8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgY29tcGxleDxkb3VibGU+IHBvaW50OwojZGVmaW5lIG1hcGlpIG1hcDxpbnQsIGludD4KI2RlZmluZSBkZWJ1ZyhhKSBjb3V0IDw8ICNhIDw8ICI6ICIgPDwgYSA8PCBlbmRsCiNkZWZpbmUgZGVidWdhMShhLCBsLCByKSBmdG8oaSwgbCwgcikgY291dCA8PCBhW2ldIDw8ICIgIjsgY291dCA8PCBlbmRsCiNkZWZpbmUgZmR0byhpLCByLCBsKSBmb3IoaW50IGkgPSAocik7IGkgPj0gKGwpOyAtLWkpCiNkZWZpbmUgZnRvKGksIGwsIHIpIGZvcihpbnQgaSA9IChsKTsgaSA8PSAocik7ICsraSkKI2RlZmluZSBmb3JpdChpdCwgdmFyKSBmb3IoX190eXBlb2YodmFyLmJlZ2luKCkpIGl0ID0gdmFyLmJlZ2luKCk7IGl0ICE9IHZhci5lbmQoKTsgaXQrKykKI2RlZmluZSBmb3JyaXQocml0LCB2YXIpIGZvcihfX3R5cGVvZih2YXIucmJlZ2luKCkpIHJpdCA9IHZhci5yYmVnaW4oKTsgcml0ICE9IHZhci5yZW5kKCk7IHJpdCsrKQojZGVmaW5lIGlpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgaWlpIHBhaXI8aW50LCBpaT4KI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1heE4gMTAwNQojZGVmaW5lIG9vIDEwMDAwMDAwMDAwMDAwMDAwMDdMTAojZGVmaW5lIHN6KGEpIChpbnQpYS5zaXplKCkKCmNvbnN0IGRvdWJsZSBQSSA9IGFjb3MoLTEuMCk7Cgpkb3VibGUgZlJhbmQoZG91YmxlIGZNaW4sIGRvdWJsZSBmTWF4KQp7CiAgICBkb3VibGUgZiA9IChkb3VibGUpcmFuZCgpIC8gUkFORF9NQVg7CiAgICByZXR1cm4gZk1pbiArIGYgKiAoZk1heCAtIGZNaW4pOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KVCBtaW4oVCBhLCBUIGIsIFQgYykgewogICAgcmV0dXJuIG1pbihhLCBtaW4oYiwgYykpOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KVCBtYXgoVCBhLCBUIGIsIFQgYykgewogICAgcmV0dXJuIG1heChhLCBtYXgoYiwgYykpOwp9CgppbnQgblRlc3QsIFIsIEIsIEMsIE1bbWF4Tl0sIFNbbWF4Tl0sIFBbbWF4Tl07Cgpib29sIENoZWNrKGxsIHgpIHsKICAgIHZlY3RvcjxpbnQ+IGI7CiAgICBmdG8oaSwgMSwgQykKICAgICAgICBpZiAoeCA+PSBQW2ldKSBiLnBiKG1pbigxTEwqTVtpXSwgKHgtUFtpXSkvU1tpXSkpOwoKICAgIHNvcnQoYi5iZWdpbigpLCBiLmVuZCgpKTsKICAgIHJldmVyc2UoYi5iZWdpbigpLCBiLmVuZCgpKTsKCiAgICBsbCBzdW0gPSAwOwogICAgZnRvKGksIDAsIG1pbihzeihiKSwgUiktMSkgc3VtICs9IGJbaV07CiAgICByZXR1cm4gc3VtID49IEI7Cn0KCmludCBtYWluICgpIHsKICAgIHNjYW5mKCIlZCIsICZuVGVzdCk7CiAgICBmdG8oaVRlc3QsIDEsIG5UZXN0KSB7CiAgICAgICAgcHJpbnRmKCJDYXNlICMlZDogIiwgaVRlc3QpOwogICAgICAgIHNjYW5mKCIlZCVkJWQiLCAmUiwgJkIsICZDKTsKICAgICAgICBmdG8oaSwgMSwgQykgc2NhbmYoIiVkJWQlZCIsICZNW2ldLCAmU1tpXSwgJlBbaV0pOwoKICAgICAgICBsbCBsbyA9IDEsIGhpID0gb28sIHJlcyA9IDA7CiAgICAgICAgd2hpbGUgKGxvIDw9IGhpKSB7CiAgICAgICAgICAgIGxsIG1pZCA9IChsbytoaSkvMjsKICAgICAgICAgICAgaWYgKENoZWNrKG1pZCkpIHsKICAgICAgICAgICAgICAgIHJlcyA9IG1pZDsKICAgICAgICAgICAgICAgIGhpID0gbWlkLTE7CiAgICAgICAgICAgIH0gZWxzZSBsbyA9IG1pZCsxOwogICAgICAgIH0KCiAgICAgICAgcHJpbnRmKCIlbGxkXG4iLCByZXMpOwogICAgfQoKICAgIHJldHVybiAwOwp9