P9124 [USACO23FEB] Bakery S

Bessie 开了一家面包店! 在她的面包店里，Bessie 有一个烤箱，可以在 $t_C$ 的时间内生产一块饼干或在 $t_M$ 单位时间内生产一块松糕。 $(1 \le t_C,t_M \le 10^9)$。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产 $A$ 块饼干和 $B$ 块松饼，需要 $A\cdot t_C+B\cdot t_M$ 单位的时间。 Bessie的 $N (1\le N\le 100)$ 朋友都想一个一个地去面包店。第 $i$ 个朋友一进门就会点 $a_i(1 \le a_i \le 10^9)$ 块饼干和 $b_i(1 \le b_i \le 10^9)$ 块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第 $i$ 个朋友只愿意等 $c_i(a_i+b_i \le c_i \le 2 \cdot 10^{18})$ 个单位的时间，然后就伤心地离开。 Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她不能将她的烤箱升级到花费小于等于 $0$ 的时间，但她可以选择在她的朋友到来之前将她的烤箱升级多少次，只要生产一块饼干和生产一个松饼所需的时间都严格保持为正数。 对于每一个 $T(1\le T\le 100)$ 的测试案例，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

无

无

### Explanation for Sample 1 In the first test case, Bessie can pay $11$ moonies to decrease the time required to produce a cookie by $4$ and a muffin by $7$, so that her oven produces cookies in $3$ units of time and muffins in $2$ units of time. Then she can satisfy the first friend in $18$ units of time, the second friend in $14$ units of time, and the third friend in $5$ units of time, so none of them will get sad and leave. In the second test case, Bessie should decrease the time required to produce a cookie by $6$ and a muffin by $0$. ### SCORING - Inputs $2-4$: $N \le 10,t_C,t_M \le 1000$ - Inputs $5-11$: No additional constraints.