Gruppindelning

문제

$NN$ 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}a\_i$, $b_{i}b\_i$ och $c_{i}c\_i$. Person nummer $ii$ kan vara ledare för en grupp med $x\le c_{i}x\; \backslash le\; c\_i$ personer (om $c_i=1c\_i=1$ måste person $ii$ vara helt ensam i sin grupp om hen ska vara ledare). Gruppens styrka definieras då som heltalet $a_i\cdot x+b_{i}a\_i\backslash cdot\; x\; +\; b\_i$. Din uppgift är att dela in personerna i grupper så att summan av styrkorna hos grupperna maximeras.

입력

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

Därefter följer $NN$ rader med tre heltal vardera: $a_{i}a\_i$, $b_{i}b\_i$ och $c_{i}c\_i$ ($-{10}^9\le a_i,b_i\le {10}^9-10^9\; \backslash le\; a\_i,\; b\_i\; \backslash le\; 10^9$, $1\le c_i\le N1\; \backslash le\; c\_i\; \backslash le\; N$).

출력

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

힌트

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(10\; \backslash cdot\; 2\; +\; 7)\; +\; (-1\; \backslash cdot\; 1\; +\; 20)\; +\; (5\; \backslash 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(10\; \backslash cdot\; 2\; +\; -20)\; +\; (11\; \backslash 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