Problem B
Gruppindelning

$N$ personer ska delas in i grupper. Varje person ska vara med i exakt en grupp, och varje grupp ska ha exakt en ledare. Varje person har tre heltal som beskriver deras ledaregenskaper: $a_ i$, $b_ i$ och $c_ i$. Person nummer $i$ kan vara ledare för en grupp med $x \le c_ i$ personer (om $c_ i=1$ måste person $i$ vara helt ensam i sin grupp om hen ska vara ledare). Gruppens styrka definieras då som heltalet $a_ i\cdot x + b_ i$. Din uppgift är att dela in personerna i grupper så att summan av styrkorna hos grupperna maximeras.

Indata

Den första raden av indata innehåller ett heltal $N$ ($1 \le N \le 4000$): antalet personer.

Därefter följer $N$ rader med tre heltal vardera: $a_ i$, $b_ i$ och $c_ i$ ($-10^9 \le a_ i, b_ i \le 10^9$, $1 \le c_ i \le N$).

Utdata

Skriv ut ett tal: den största summa av styrkor som kan uppnås.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempel

I det första exemplet kan den högsta styrka uppnås t.ex. genom att dela in personerna i tre grupper: en bestående av person 1 och 4 (med 1 som ledare), en med person 3 och 5 (med 3 som ledare), och en med person 2. Detta ger $(10 \cdot 2 + 7) + (-1 \cdot 1 + 20) + (5 \cdot 2 + 10) = 66$ styrka. Testfallet skulle kunna finnas med i testgrupp 3.

I det andra exemplet kan högsta styrka uppnås t.ex. genom att dela in personerna i två grupper: en med personer 1, 2 och 3 (med 3 som ledare), och en med personer 4 och 5 (med 4 som ledare). Detta ger $(10 \cdot 2 + -20) + (11 \cdot 3 + -30) = 3$ styrka. Testfallet skulle kunnas finnas med i testgrupp 4.

5
10 7 2
-1 20 4
5 10 3
2 2 2
2 2 2

66

5
6 -40 4
7 -40 4
10 -20 2
11 -30 3
12 -10 1

3

4
1000000000 1000000000 2
-1000000000 10 2
900000000 -1000000000 2
-20 -25 1

3800000000