题目描述

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 \times 10^{18}$）个单位的时间，然后就伤心地离开。

Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她可以选择在她的朋友到来之前将她的烤箱升级的次数，当且仅当生产一块饼干和生产一个松饼所需的时间都是正数。

本题共有 $T$ 组数据（$1\le T\le 100$），对于每一组数据，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

输入格式

第一行输入 $T$，表示测试用例的数量。

每个测试用例的第一行，输入 $N$，$t_C$，$t_M$。接下来的 $N$ 行依次输入三个整数 $a_i$，$b_i$，$c_i$。

输出格式

每行单独输出每个测试用例中 Bessie 需要花费的最少钱数。

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

提示

样例解释 1

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

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

数据规模与约定

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

翻译 @ __11jiang08__