그룹 나누기

$N$명의 사람을 여러 그룹으로 나눈다. 각 사람은 정확히 한 그룹에 속하고, 각 그룹에는 정확히 한 명의 리더가 있다. 사람 $i$는 리더로서의 능력을 나타내는 정수 $a\_i$, $b\_i$, $c\_i$를 가진다. 사람 $i$는 $x \le c\_i$를 만족하는 $x$명의 그룹에서 리더가 될 수 있다. $c\_i=1$이면 사람 $i$는 리더가 되려면 그룹에 혼자 있어야 한다. 이 그룹의 강도는 정수 $a\_i\cdot x + b\_i$이다. 그룹들의 강도 합이 최대가 되도록 사람들을 나누어라.

첫 줄에 사람의 수를 나타내는 정수 $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에 포함되어 있을 수 있다.