시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB422100.000%

문제

$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.

입력

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$).

출력

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

예제 입력 1

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

예제 출력 1

66

예제 입력 2

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

예제 출력 2

3

예제 입력 3

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

예제 출력 3

3800000000

힌트

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.

출처

Olympiad > Swedish Olympiad in Informatics > 2021 > KATT ?번

  • 문제를 만든 사람: Nils Gustafsson