//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;
}