您正在参加 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$$$ 的最佳订单之一。