F. Вася и бесконечные кредиты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася решил купить себе шикарную новую машину. К сожалению, ему немного не хватает денег. Сейчас у него есть 0 бурлей.

В местном банке есть $$$n$$$ предложений по кредитам. Каждое предложение описывается тремя числами $$$a_i$$$, $$$b_i$$$ и $$$k_i$$$. Предложения пронумерованы от $$$1$$$ до $$$n$$$. Если Вася пользуется $$$i$$$-м предложением, то банк выдает ему $$$a_i$$$ бурлей в начале месяца, а потом забирает по $$$b_i$$$ бурлей в конце каждого из $$$k_i$$$ следующих месяцев (включая месяц, в который кредит был взят). Вася может брать предложения в любом порядке.

В каждый месяц Вася может брать не более одного кредитного предложения. К тому же каждое кредитное предложение может быть использовано не более одного раза. Несколько кредитов могут быть активны в одно и то же время. Это подразумевает, что Вася платит банку сумму $$$b_i$$$ по всем $$$i$$$ активных кредитов в конце каждого из месяцев.

Вася хочет купить машину в середине некоторого месяца. Он просто берет все деньги, которые у него есть на текущий момент, и покупает машину ровно этой цены.

Васю не особо заботит, сколько он должен будет заплатить банку после покупки машины. Он просто уедет на своей машине из страны, так что банк не сможет его найти.

Какая максимальная цена может быть у новой машины?

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 500$$$) — количество кредитных предложений.

В каждой из следующих $$$n$$$ строк записаны по три целых числа $$$a_i$$$, $$$b_i$$$ и $$$k_i$$$ ($$$1 \le a_i, b_i, k_i \le 10^9$$$).

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

Выведите одно целое число — максимальную цену машины.

Примеры
Входные данные
4
10 9 2
20 33 1
30 115 1
5 3 2
Выходные данные
32
Входные данные
3
40 1 2
1000 1100 5
300 2 1
Выходные данные
1337
Примечание

В первом примере оптимальная последовательность взятых кредитов такова: 4 $$$\rightarrow$$$ 3.

Количество бурлей у Васи меняется следующим образом: 5 $$$\rightarrow$$$ 32 $$$\rightarrow$$$ -86 $$$\rightarrow$$$ .... Он забирает деньги в середине второго месяца (32 бурля) и покупает машину.

Отрицательное число бурлей значит, что Вася должен заплатить банку эту сумму денег.

Во втором примере оптимальная последовательность взятых кредитов такова: 3 $$$\rightarrow$$$ 1 $$$\rightarrow$$$ 2.

Количество бурлей у Васи меняется следующим образом: 0 $$$\rightarrow$$$ 300 $$$\rightarrow$$$ 338 $$$\rightarrow$$$ 1337 $$$\rightarrow$$$ 236 $$$\rightarrow$$$ -866 $$$\rightarrow$$$ ....