#include <stdio.h>
#include <vector>
#include <algorithm>
#define pb push_back
#define lli long long int
using namespace std;

const int MAX_C = (int)1e3 + 5;
const lli INF_LL = (lli)2e18;

int m[MAX_C];
int s[MAX_C];
int p[MAX_C];

int main(void) {
    int t;
    int r, b, c;

    scanf(" %d", &t);
    for (int test = 1; test <= t; test++) {
        scanf(" %d %d %d", &r, &b, &c);
        for (int i = 0; i < c; i++) {
            scanf(" %d %d %d", &m[i], &s[i], &p[i]);
        }

        lli low = 0;
        lli high = INF_LL;
        lli best = 0;
        while(low <= high) {
            lli mid = (low + high) / 2;
            lli need = b;
            vector <lli> bits;

            for (int i = 0; i < c; i++) {
                bits.pb(min(1LL * m[i], max(0LL, (mid - p[i]) / s[i])));
            }
            sort(bits.begin(), bits.end());
            reverse(bits.begin(), bits.end());
            for (int i = 0; i < r && i < c; i++) {
                need -= bits[i];
            }

            if (need <= 0) {
                best = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        printf("Case #%d: %lld\n", test, best);
    }
    return 0;
}