Вы участвуете в раунде Codeforces с \(n\) задачами.
На решение каждой задачи вы тратите ровно одну минуту, время на отправку решения можно не учитывать. В каждый момент времени вы можете решать не более одной задачи. Раунд начинается в момент времени \(0\), поэтому свою первую посылку вы можете сделать в момент времени \(t \ge 1\) минут. Когда вы отправляете решение, вы всегда правильно решаете задачу.
Получаемые баллы за \(i\)-ю задачу могут быть описаны тремя целыми числами \(k_i\), \(b_i\) и \(a_i\). Если вы решите эту задачу по прошествии \(t\) минут, вы получите \(\max(b_i - k_i \cdot t,a_i)\) баллов.
Ваша задача — выбрать порядок решения всех этих \(n\) задач, чтобы получить максимальное количество очков. Можете считать, что раунд достаточно длинный, и вы успеете решить все задачи.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую одно целое число — максимальный балл, который вы можете получить.
Примечание
Во втором наборе входных данных баллы всех задач на каждой минуте перечислены ниже.
| Время | \(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\) балла.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3999961003
53
78
180
|