题目描述

These days, robots can drive cars, but can they throw a good party? The Code Jam team's research into this topic is still at an early stage. We just deployed $\mathbf{R}$ robot shoppers to our local supermarket to buy party supplies for our World Finals in Toronto, but their first-order model of a Canadian party was very simple: they just bought $\mathbf{B}$ "bits" (a bit being a small donut-like treat found in the area). We will work on improving their AI later, but for now, we want to help them purchase all of those bits as quickly as possible.

The supermarket has $\mathbf{C}$ cashiers who can scan customers' purchases. The $i$-th cashier will:

• accept a maximum of $\mathbf{M}_{\mathbf{i}}$ items per customer
• take $\mathbf{S}_{\mathbf{i}}$ seconds to scan each item
• spend a further $\mathbf{P}_{\mathbf{i}}$ seconds handling payment and packaging up the bits.

That is, a customer who brings $\mathrm{N}$ bits to the $i$-th cashier (where $\mathrm{N}$ must be less than or equal to $\mathbf{M}_{\mathbf{i}}$ ) will spend a total of $\mathbf{S}_{\mathbf{i}} \times \mathrm{N}+\mathbf{P}_{\mathbf{i}}$ seconds interacting with that cashier.

Before the robots interact with any cashiers, you will distribute the bits among the robots however you want. (Bits must remain intact; you cannot break them up into fractional pieces!) Any robot that gets no bits will not get to interact with a cashier, and will go away disappointed.

Then, for each robot with at least one bit, you will choose a different single cashier. (Two robots cannot use the same cashier, and a robot cannot use more than one cashier.) The robots all start interacting with their cashiers at time 0 . Note that once a robot finishes interacting with its cashier, it cannot be given more bits and cannot interact with other cashiers.

If you help the robots make optimal choices, what is the earliest time at which all of the robots can finish interacting with their cashiers?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each begins with one line with three integers $\mathbf{R}, \mathbf{B}$, and $\mathbf{C}$ : the numbers of robot shoppers, bits, and cashiers. Then, there are $\mathbf{C}$ more lines. The $i$-th of these represents the $i$-th cashier, and it has three integers $\mathbf{M}_{\mathbf{i}}, \mathbf{S}_{\mathbf{i}}$, and $\mathbf{P}_{\mathbf{i}}$ : the maximum number of bits, scan time per bit (in seconds), and payment/packaging time (in seconds) for that cashier, as described above.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the earliest time (in seconds) at which all robots can finish interacting with their cashiers.

3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1

Case #1: 5
Case #2: 4
Case #3: 7

提示

Sample Explanation

In Sample Case #1, there are two robots, two bits, and two cashiers, and each cashier can only handle one item. So, you must give one bit to each robot. Cashier 1 takes 5 seconds, and Cashier 2 takes 3 seconds, so the time required is 5 seconds.

Sample Case #2 is similar to the previous case, except that now Cashier 2 can handle up to 2 items. So, it is best to give all the bits to one robot and have that robot use Cashier 2. This takes 1 second per item plus 2 seconds $=4$ seconds.

In Sample Case #3, the optimal strategy is to send one robot with 2 bits to cashier 2, and two robots with 1 bit each to any of the other cashiers.

Limits

• $1 \leqslant \mathbf{T} \leqslant 100$.
• $1 \leqslant \mathbf{M}_{\mathbf{i}} \leqslant 10^{9}$, for all $i$.
• $1 \leqslant \mathbf{S}_{\mathbf{i}} \leqslant 10^{9}$, for all $i$.
• $1 \leqslant \mathbf{P}_{\mathbf{i}} \leqslant 10^{9}$, for all $i$.
• The sum of the $\mathbf{R}$ largest values of $\mathbf{M}_{\mathbf{i}} \geqslant \mathbf{B}$. (It is possible for at least one subset of $\mathbf{R}$ cashiers to handle all of the bits.)

Test set 1 (11 Pts, Visible)

• $1 \leqslant \mathbf{R} \leqslant \mathbf{C} \leqslant 5$.
• $1 \leqslant \mathbf{B} \leqslant 20$.

Test set 2 (21 Pts, Hidden)

• $1 \leqslant \mathbf{R} \leqslant \mathbf{C} \leqslant 1000$.
• $1 \leqslant \mathbf{B} \leqslant 10^{9}$.