H. Разбалловка Codeforces
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы участвуете в раунде 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$$$.

Выходные данные

Для каждого набора входных данных выведите строку, содержащую одно целое число — максимальный балл, который вы можете получить.

Пример
Входные данные
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
Выходные данные
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$$$ балла.