Optimal Cooking Schedule

You are given n ingredients. For each ingredient i (1 ≤ i ≤ n), you are given three integers a_i, b_i and c_i. If ingredient i is finished at time t, then its flavor score is calculated as:

$a_i - t \times b_i$

Cooking ingredient i takes exactly c_i time. At the start, the time is t = 0 and you cook ingredients one by one. The finishing time of an ingredient is the sum of the cooking times of all ingredients cooked before it plus its own cooking time. Your task is to determine a cooking order (schedule) for all ingredients such that the total flavor score is maximized.

Hint: Maximizing the total flavor score is equivalent to minimizing the total penalty given by the sum of t × b_i over all ingredients. A greedy strategy based on an appropriate sort order is recommended.

inputFormat

The first line contains a single integer n (the number of ingredients).

Each of the next n lines contains three space-separated integers: a_i, b_i and c_i.

outputFormat

Output a single integer, which is the maximum total flavor score that can be achieved.

sample

3
4 2 1
5 3 3
3 1 2

-8