const int OO = (int)(1e9 + 7);
const int MAXN = (int)(1e3+5);

struct Cashier
{
    long long m;
    long long s, p;
};

Cashier a[MAXN];
bool used[MAXN];
int r, b, c;

bool check(long long t)
{
    memset(used, false, sizeof(used));
    int num = b;
    for(int i = 1; i <= r; ++i)
    {
        if (num <= 0)
            break;
        int pos = 0;
        int maxItems = 0;
        for(int j = 1; j <= c; ++j)
            if (!used[j])
            {
                int items = min(a[j].m, (t - a[j].p) / a[j].s);
                if (items > maxItems)
                    pos = j, maxItems = items;
            }
        num -= maxItems;
        used[pos] = true;
    }
    return num <= 0;
}

void Inp()
{
    int t;
    cin >> t;
    For(iTest, 1, t)
    {
        cout << "Case #" << iTest << ": ";
        cin >> r >> b >> c;
        for(int i = 1; i <= c; ++i)
            cin >> a[i].m >> a[i].s >> a[i].p;
        long long lo = 0, hi = 1LL * OO * OO + OO, mid = (lo + hi) / 2;
        while (lo != mid && hi != mid)
        {
            if (check(mid))
                hi = mid;
            else
                lo = mid;
            mid = (lo + hi) / 2;
        }
        for(long long i = lo; i <= hi; ++i)
            if (check(i))
            {
                cout << i;
                break;
            }
        cout << '\n';
    }
}