그룹 나누기

$N$명의 사람을 그룹으로 나누어야 한다. 각 사람은 정확히 하나의 그룹에 속해야 하며, 각 그룹에는 정확히 한 명의 리더가 있어야 한다. 각 사람에게는 리더로서의 특성을 나타내는 세 정수 $a_i$, $b_i$, $c_i$이 있다. 번호가 $i$인 사람은 사람이 $x \le c_i$명인 그룹의 리더가 될 수 있다 ($c_i=1$인 경우, $i$번 사람이 리더가 되려면 자신의 그룹에 완전히 혼자 있어야 한다). 이때 그룹의 힘은 정수 $a_i\cdot x + b_i$로 정의된다. 그룹들의 힘의 합이 최대가 되도록 사람들을 그룹으로 나누는 것이 과제이다.

점수

여러 테스트 케이스 그룹으로 해답을 평가한다. 한 그룹에서 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$10$| $N \le 15$

$2$ |$15$| $N \le 200$

$3$ |$15$| $b_i \ge 0$

$4$ |$23$| $b_i \le 0$

$5$ |$37$| 추가 제한 없음

입력의 첫째 줄에는 사람의 수를 나타내는 정수 $N$ ($1 \le N \le 4000$)이 주어진다.

그다음 $N$개의 줄에 각각 세 정수 $a_i$, $b_i$, $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le N$)이 주어진다.

달성할 수 있는 힘의 합의 최댓값을 정수 하나로 출력한다.

첫 번째 예제에서는 예를 들어 사람들을 세 그룹으로 나누어 힘의 최댓값을 달성할 수 있다. 한 그룹은 1번 사람과 4번 사람으로 구성되고(1번 사람이 리더), 한 그룹은 3번 사람과 5번 사람으로 구성되며(3번 사람이 리더), 나머지 한 그룹에는 2번 사람이 속한다. 이렇게 하면 힘은 $(10 \cdot 2 + 7) + (-1 \cdot 1 + 20) + (5 \cdot 2 + 10) = 66$이 된다. 이 테스트 케이스는 테스트 그룹 3에 포함될 수 있다.

두 번째 예제에서는 예를 들어 사람들을 두 그룹으로 나누어 힘의 최댓값을 달성할 수 있다. 한 그룹에는 1, 2, 3번 사람이 속하고(3번 사람이 리더), 다른 그룹에는 4번 사람과 5번 사람이 속한다(4번 사람이 리더). 이렇게 하면 힘은 $(10 \cdot 2 + -20) + (11 \cdot 3 + -30) = 3$이 된다. 이 테스트 케이스는 테스트 그룹 4에 포함될 수 있다.