题目描述

岩石怪物 Duda 住在魔法森林里，他收集了 $N$ 块能量石作为午餐。因为他的嘴很小，所以他一次只能吃一块石头。有些石头比其他石头更难啃！第 $i$ 块石头需要他花费 $S_i$ 秒才能吃完。

Duda 吃能量石是为了获得能量。不同的石头给他提供的能量也不同。而且，石头的能量会随着时间流失。第 $i$ 块石头初始含有 $E_i$ 单位能量，并且每秒会流失 $L_i$ 单位能量。当 Duda 开始吃一块石头时，他会立即获得该石头当前所含的所有能量（无论实际吃完这块石头需要多长时间）。石头的能量一旦降到零就不会再继续减少。

Duda 通过吃这些石头最多能获得多少能量？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示 Duda 拥有的能量石数量。随后有 $N$ 行，第 $i$ 行包含三个整数 $S_i$、$E_i$ 和 $L_i$，含义如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Duda 通过吃石头能获得的最大能量值。

2
3
10 4 1000
10 3 1000
10 8 1000
2
10 2 0
10 3 0

Case #1: 8
Case #2: 5

2
4
20 10 1
5 30 5
100 30 1
5 80 60
2
12 300 50
5 200 0

Case #1: 105
Case #2: 500

提示

样例

在样例 #1 中，有 $N = 3$ 块石头。无论 Duda 先吃哪块石头，等他吃完后，另外两块石头的能量都会降为零。因此他应该吃第三块石头，获得 $8$ 单位能量。

额外样例 – 测试集 2

下面的额外样例符合测试集 2 的限制范围。它不会用于测试你提交的解答。

在样例 #1 中，有 $N = 4$ 块石头。Duda 吃石头的一种可能顺序是：

• 吃第四块石头。耗时 $5$ 秒，获得 $80$ 单位能量。
• 吃第二块石头。再耗时 $5$ 秒，获得 $5$ 单位能量（第二块石头初始有 $30$ 能量，经过 $5$ 秒后流失了 $25$ 单位能量）。
• 吃第三块石头。再耗时 $100$ 秒，获得 $20$ 单位能量（第三块石头初始有 $30$ 能量，经过 $10$ 秒后流失了 $10$ 单位能量）。
• 吃第一块石头。再耗时 $20$ 秒，获得 $0$ 单位能量（第一块石头初始有 $10$ 单位能量，经过 $110$ 秒后能量已全部流失）。

这样他总共获得 $105$ 单位能量，这是他能做到的最佳结果。因此答案为 $105$。

在样例 #2 中，有 $N = 2$ 块石头。Duda 可以：

• 吃第一块石头。耗时 $12$ 秒，获得 $300$ 单位能量。
• 吃第二块石头。耗时 $5$ 秒，获得 $200$ 单位能量（第二块石头不会随时间流失能量！）。

因此答案为 $500$。

限制条件

$1 \le T \le 100$。

$1 \le N \le 100$。

$1 \le S_i \le 100$。

$1 \le E_i \le 10^5$。

$0 \le L_i \le 10^5$。

测试集 1（可见）

所有石头所需吃的时间相同。即：对于所有 $i$ 和 $j$，$S_i = S_j$。

测试集 2（隐藏）

除通用限制外，没有额外限制。

翻译由 DeepSeek V4 Pro 完成