Вы участвуете в раунде 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$$$), которые означают, что вы получите $$$\max(b_i - k_i \cdot t,a_i)$$$ баллов, если решите эту $$$i$$$-ю задачу на $$$t$$$-й минуте.
Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите строку, содержащую одно целое число — максимальный балл, который вы можете получить.
4410000 1000000000 200610000 1000000000 99992 999991010 10101000000000 1000000000 99999999961 8 19 29 42 14 34 13 12 19 510 12 584 10 14 19 81 14 34 15 62 9 61 11 102 19 124 19 14105 12 75 39 122 39 113 23 155 30 113 17 135 29 143 17 113 36 183 9 8
3999961003 53 78 180
Во втором наборе входных данных баллы всех задач на каждой минуте перечислены ниже.
Время | $$$1$$$ | $$$2$$$ | $$$3$$$ | $$$4$$$ | $$$5$$$ | $$$6$$$ |
Задача $$$1$$$ | $$$7$$$ | $$$6$$$ | $$$5$$$ | $$$\color{red}{4}$$$ | $$$3$$$ | $$$2$$$ |
Задача $$$2$$$ | $$$\color{red}{20}$$$ | $$$11$$$ | $$$4$$$ | $$$4$$$ | $$$4$$$ | $$$4$$$ |
Задача $$$3$$$ | $$$12$$$ | $$$10$$$ | $$$\color{red}{8}$$$ | $$$6$$$ | $$$4$$$ | $$$3$$$ |
Задача $$$4$$$ | $$$9$$$ | $$$5$$$ | $$$1$$$ | $$$1$$$ | $$$\color{red}{1}$$$ | $$$1$$$ |
Задача $$$5$$$ | $$$17$$$ | $$$\color{red}{15}$$$ | $$$13$$$ | $$$11$$$ | $$$9$$$ | $$$7$$$ |
Задача $$$6$$$ | $$$5$$$ | $$$5$$$ | $$$5$$$ | $$$5$$$ | $$$5$$$ | $$$\color{red}{5}$$$ |
Красным цветом показан один из оптимальных порядков решения задач, который дает $$$53$$$ балла.
Название |
---|