Bakery Upgrade Challenge

Bessie has opened a bakery! In her bakery, Bessie has an oven that can produce a cookie in \(t_C\) units of time or a muffin in \(t_M\) units of time \( (1 \le t_C,t_M \le 10^9)\). Due to space constraints, Bessie can only produce one pastry at a time, so to produce \(A\) cookies and \(B\) muffins, it takes

[ A \cdot t_C + B \cdot t_M \text{ units of time.} ]

Bessie's \(N\) \( (1\le N \le 100)\) friends come to the bakery one by one. The \(i\)-th friend orders \(a_i\) cookies and \(b_i\) muffins \( (1 \le a_i, b_i \le 10^9)\) immediately upon arriving. Since she cannot store pastries, she starts production as soon as an order is received. Moreover, the \(i\)-th friend will wait at most \(c_i\) units of time \( (a_i+b_i \le c_i \le 2\cdot 10^{18})\) before getting upset and leaving.

Before her friends arrive, Bessie has the option to upgrade her oven. With one mooney she can reduce the production time for either a cookie or a muffin by 1 unit. She may perform as many integer upgrades as she wishes as long as the production times remain strictly positive.

For each of \(T\) test cases \( (1 \le T \le 100)\), determine the minimum number of moonies Bessie must spend on upgrades so that her bakery can satisfy all her friends.

inputFormat

The first line of input contains a single integer \(T\), the number of test cases.

Each test case begins with a line containing three integers \(t_C\), \(t_M\) and \(N\) — the time to produce a cookie (in units), the time to produce a muffin (in units), and the number of friends.

Then \(N\) lines follow. The \(i\)-th of these lines contains three integers \(a_i\), \(b_i\) and \(c_i\) representing the number of cookies, the number of muffins ordered by the \(i\)-th friend, and the maximum time that friend is willing to wait.

It is guaranteed that \(1 \le t_C,t_M \le 10^9\), \(1 \le N \le 100\), \(1 \le a_i, b_i \le 10^9\) and \(a_i+b_i \le c_i \le 2\cdot 10^{18}\).

outputFormat

For each test case, output a single integer — the minimum number of moonies Bessie needs to spend on upgrades so that she can serve all her friends in time.

sample

3
3 5 1
1 1 7
3 6 2
1 1 9
2 2 15
4 4 1
3 3 15

1
2
3