P16727 [GKS 2019 #B] Energy Stones

岩石怪物 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 通过吃石头能获得的最大能量值。

### 样例 在样例 #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 完成