← 返回题目列表

Codeforces · 1787/H

H. Codeforces 记分板

中文机器翻译题面 查看原题

您正在参加 Codeforces 回合,并遇到 $$$n$$$ 问题。

你只花一分钟来解决每个问题,提交问题所花费的时间可以忽略不计。任何时候你最多只能解决一个问题。比赛于 $$$0$$$ 开始,因此您可以在 $$$t \ge 1$$$ 分钟内随时进行首次提交。每当您提交问题时,它总是会被接受。

第$$$i$$$问题的得分可以用三个整数$$$k_i$$$、$$$b_i$$$和$$$a_i$$$表示。如果您在 $$$t$$$ 分钟内解决该问题,您将获得 $$$\max(b_i - k_i \cdot t,a_i)$$$ 分。

你的任务是选择一个顺序来解决所有这些 $$$n$$$ 问题以获得最大可能的分数。您可以假设比赛的时间足够长以解决所有问题。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 问题数。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含三个整数 $$$k_i$$$, $$$b_i$$$, $$$a_i$$$ ($$$1\le k_i,b_i,a_i\le 10^9$$$; $$$a_i < b_i$$$),表示你得到如果您在 $$$t$$$ 分钟解决第 $$$i$$$ 个任务,则得分为 $$$\max(b_i - k_i \cdot t,a_i)$$$。

保证 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一行包含单个整数 - 您可以获得的最高分数。

示例

输入 #1

4
4
10000 1000000000 2006
10000 1000000000 9999
2 999991010 1010
1000000000 1000000000 999999999
6
1 8 1
9 29 4
2 14 3
4 13 1
2 19 5
10 12 5
8
4 10 1
4 19 8
1 14 3
4 15 6
2 9 6
1 11 10
2 19 12
4 19 14
10
5 12 7
5 39 12
2 39 11
3 23 15
5 30 11
3 17 13
5 29 14
3 17 11
3 36 18
3 9 8

输出 #1

3999961003
53
78
180

注意

在第二个测试用例中,下面列出了每分钟所有问题的得分。

时间$$$1$$$$$$2$$$$$3$$$$$$4$$$$$$5$$$$$6$$$问题 $$$1$$$$$7$$$$$6$$$$$$5$$$$$$\颜色{红色}{4}$$$$$$3$$$$$$2$$$问题$$$2$$$$$$\颜色{红色}{20}$$$$$$11$$$$$$4$$$$$$4$$$$$$4$$$$$$4$$$问题$$$3$$$$$12$$$$$$10$$$$$$\颜色{红色}{8}$$$$$$6$$$$$4$$$$$$3$$$问题 $$$4$$$$$$9$$$$$$5$$$$$$1$$$$$$1$$$$$$\颜色{红色}{1}$$$$$$1$$$问题$$$5$$$$$$17$$$$$$\颜色{红色}{15}$$$$$$13$$$$$$11$$$$$$9$$$$$7$$$问题$$$6$$$$$$5$$$$$$5$$$$$$5$$$$$$5$$$$$$5$$$$$$\颜色{红色}{5}$$$

以红色显示的点表示得分为 $$$53$$$ 的最佳订单之一。