CF1107F.Vasya and Endless Credits

Vasya wants to buy himself a nice new car. Unfortunately, he lacks some money. Currently he has exactly 0 burles.

However, the local bank has $n$ credit offers. Each offer can be described with three numbers $a_i$, $b_i$ and $k_i$. Offers are numbered from $1$ to $n$. If Vasya takes the $i$-th offer, then the bank gives him $a_i$ burles at the beginning of the month and then Vasya pays bank $b_i$ burles at the end of each month for the next $k_i$ months (including the month he activated the offer). Vasya can take the offers any order he wants.

Each month Vasya can take no more than one credit offer. Also each credit offer can not be used more than once. Several credits can be active at the same time. It implies that Vasya pays bank the sum of $b_i$ over all the $i$ of active credits at the end of each month.

Vasya wants to buy a car in the middle of some month. He just takes all the money he currently has and buys the car of that exact price.

Vasya don't really care what he'll have to pay the bank back after he buys a car. He just goes out of the country on his car so that the bank can't find him anymore.

What is the maximum price that car can have?

瓦西娅想给自己买一辆漂亮的新车。不幸的是，他手头的钱不够。目前他恰好有 0 卢布。

然而，当地银行提供了 $n$ 种信贷方案。每种方案可用三个数 $a_i$、$b_i$ 和 $k_i$ 描述。这些方案编号从 $1$ 到 $n$。若瓦西娅选择第 $i$ 种方案，则银行会在该月月初向他发放 $a_i$ 卢布；随后，瓦西娅需在接下来的 $k_i$ 个月内（包括启用该方案的当月）每月月末向银行偿还 $b_i$ 卢布。瓦西娅可以按任意顺序选择这些方案。

每个月瓦西娅最多只能选择一种信贷方案。此外，每种信贷方案至多只能使用一次。多个信贷方案可同时处于生效状态。这意味着：在每月月末，瓦西娅需向银行支付所有当前生效信贷方案对应的 $b_i$ 值之和。

瓦西娅希望在某个月的月中购买汽车。此时他将自己当时拥有的全部资金取出，并恰好用这笔钱购买一辆汽车。

瓦西娅并不关心购车之后还需向银行偿还多少欠款。他只需开着新车出国，让银行再也找不到他即可。

请问：这辆汽车的最高价格是多少？

The first line contains one integer $n$ ($1 \le n \le 500$) — the number of credit offers.

Each of the next $n$ lines contains three integers $a_i$, $b_i$ and $k_i$ ($1 \le a_i, b_i, k_i \le 10^9$).

第一行包含一个整数 $n$（$1 \le n \le 500$）—— 表示信贷优惠的数量。

接下来的 $n$ 行中，每行包含三个整数 $a_i$、$b_i$ 和 $k_i$（$1 \le a_i, b_i, k_i \le 10^9$）。

Print one integer — the maximum price of the car.

输出一个整数——汽车的最高价格。

In the first example, the following sequence of offers taken is optimal: 4 $\rightarrow$ 3.

The amount of burles Vasya has changes the following way: 5 $\rightarrow$ 32 $\rightarrow$ -86 $\rightarrow$ .... He takes the money he has in the middle of the second month (32 burles) and buys the car.

The negative amount of money means that Vasya has to pay the bank that amount of burles.

In the second example, the following sequence of offers taken is optimal: 3 $\rightarrow$ 1 $\rightarrow$ 2.

The amount of burles Vasya has changes the following way: 0 $\rightarrow$ 300 $\rightarrow$ 338 $\rightarrow$ 1337 $\rightarrow$ 236 $\rightarrow$ -866 $\rightarrow$ ....

在第一个例子中，以下报价选取序列是最优的：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$ ....