Group Division

Divide $N$ people into groups. Each person belongs to exactly one group, and each group has exactly one leader. Person $i$ has three integers $a\_i$, $b\_i$, and $c\_i$ that describe their leadership ability. Person $i$ can lead a group of $x$ people if $x \le c\_i$. If $c\_i=1$, person $i$ must be alone in their group to lead. The strength of such a group is the integer $a\_i\cdot x + b\_i$. Divide the people into groups so that the sum of the group strengths is maximized.

The first line contains an integer $N$ ($1 \le N \le 4000$), the number of people. Each of the next $N$ lines contains three integers $a\_i$, $b\_i$, and $c\_i$ ($-10^9 \le a\_i, b\_i \le 10^9$, $1 \le c\_i \le N$).

Print one integer: the maximum possible sum of group strengths.

In the first sample, the maximum strength is achieved, for example, by splitting the people into three groups: one with persons 1 and 4 (leader 1), one with persons 3 and 5 (leader 3), and one with person 2. This gives $(10 \cdot 2 + 7) + (-1 \cdot 1 + 20) + (5 \cdot 2 + 10) = 66$ strength. This test case could be part of test group 3.

In the second sample, the maximum strength is achieved, for example, by splitting the people into two groups: one with persons 1, 2, and 3 (leader 3), and one with persons 4 and 5 (leader 4). This gives $(10 \cdot 2 + -20) + (11 \cdot 3 + -30) = 3$ strength. This test case could be part of test group 4.