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 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

输入格式

第一行包含 $T$，测试案例的数量。

每个测试用例都以一行开始，包含 $N$ ,$t_C$,$t_M$。然后，接下来的 $N$ 行各包含三个整数 $a_i,b_i,c_i$。

测试案例用换行符隔开。

输出格式

Bessie 需要为每个测试案例花费的最少钱数，每行一个。

样例解释 1

在第一个测试案例中，贝西可以支付 $11$ 元来减少 $4$ 单位生产一块饼干所需的 时间和 $7$ 单位生产一块松饼所需的时间，从而使她的烤箱在 $3$ 单位的时间内生产饼干，在 $2$ 单位的时间内生产松饼。那么她可以在 $18$ 单位的时间内满足第一个朋友，在 $14$ 单位的时间内满足第二个朋友，在 $5$ 单位的时间内满足第三个朋友，所以他们都不会伤心而离开。

在第二个测试案例中，贝西应该把生产一块饼干的时间减少 $6$ 单位，把生产一块松饼的时间减少 $0$ 单位。

数据规模与约定

• 输入 $2-4$：$N\le 10,t_C,t_M \le 1000$
• 输入 $5-11$，没有额外的约束。

翻译 @ __11jiang08__

输入输出样例 1

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

11
6