Bakery

题目描述

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 \leq a_i\leq 10^9$）块曲奇和 $b_i$（$1 \leq b_i \leq 10^9$）个松饼。Bessie 没有空间存放点心，所以她只会在收到订单后才开始制作。 此外，Bessie 的朋友们都很忙，因此第 $i$ 个朋友最多只愿意等待 $c_i$（$a_i + b_i \leq c_i \leq 2 \cdot 10^{18}$）单位时间，否则就会伤心并离开。 Bessie 非常不希望朋友们伤心。花 1 个 mooney，她可以升级烤箱，使制作一块曲奇所需时间减少 1，或使制作一个松饼所需时间减少 1。她不能进行非整数次升级，但她可以在朋友到来之前按需要进行任意多次升级，只要制作曲奇和制作松饼所需时间都仍然严格为正。 对于每个 $T$（$1 \leq T \leq 100$）组测试用例，请帮助 Bessie 求出她最少需要花费多少 mooney，才能让她的烘焙店满足所有朋友的需求。

输入格式

第一行包含 $T$，表示测试用例数量。 每个测试用例的第一行包含 $N$、$t_C$、$t_M$。接下来 $N$ 行每行包含三个整数 $a_i,b_i,c_i$。 相邻测试用例之间用空行分隔。

输出格式

对每个测试用例输出一行，表示 Bessie 需要花费的最少 mooney 数量。

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

提示

在第一个测试用例中，Bessie 可以支付 11 个 mooney，将制作曲奇所需时间减少 4、制作松饼所需时间减少 7，使得烤箱制作曲奇需要 3 单位时间、制作松饼需要 2 单位时间。这样她可以在 18 单位时间内满足第一个朋友，在 14 单位时间内满足第二个朋友，在 5 单位时间内满足第三个朋友，因此他们都不会伤心离开。 在第二个测试用例中，Bessie 应将制作曲奇所需时间减少 6、制作松饼所需时间减少 0。 SCORING: Inputs 2-4: $N \leq 10, t_C, t_M \leq 1000$ Inputs 5-11: 无额外限制。 题目致谢：Benjamin Qi

标签: USACO|2023|Silver

来源

USACO|2023|Silver