JOI 왕국은 금 생산으로 유명하다. JOI 왕국에서는 매년 한 번씩 불도저를 사용하여 금을 채굴한다.

JOI 왕국의 땅은 $xy$ 좌표를 가진 평면으로 나타낼 수 있다. 이 땅에는 $N$개의 지점이 있다. $i$번째 지점($1 \le i \le N$)의 좌표는 $(X_i, Y_i)$이다. 각 지점에는 금 또는 바위 중 하나만 있으며, 둘 다 있는 경우는 없다.

지점 $i$에 금이 있을 때, 이를 한 번 채굴하면 가치가 $V_i$인 금을 얻는다. 지점 $i$에 바위가 있을 때, 이를 한 번 채굴하면 바위를 얻는다. 이를 처분하는 데 드는 비용은 $C_i$이다.

우리는 다음과 같은 방법으로 불도저를 사용하여 채굴한다. 먼저, $xy$ 평면에서 서로 평행한 두 직선을 선택한다. 그런 다음, 두 평행선 사이의 영역에 있는 모든 금과 바위를 각각 한 번씩 채굴한다(두 직선 위에 놓인 금이나 바위도 포함한다).

JOI 왕국의 이익은 채굴 영역에 있는 금의 총가치에서 같은 영역에 있는 바위를 처분하는 총비용을 뺀 값이다. 우리는 JOI 왕국의 이익을 최대화하고자 한다.

과제

JOI 왕국의 최대 이익을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로부터 다음 데이터를 읽는다.

• 입력의 첫째 줄에는 금이나 바위를 채취할 수 있는 지점의 개수를 나타내는 정수 $N$이 주어진다.

• 이어지는 $N$개의 줄 중 $i$번째 줄($1 \le i \le N$)에는 공백으로 구분된 세 정수 $X_i, Y_i, W_i$가 주어진다.

  • $W_i \ge 1$이면, $i$번째 지점 $(X_i, Y_i)$에는 금이 있다. 이를 한 번 채굴하면 가치가 $V_i = W_i$인 금을 얻는다.
  • $W_i \le -1$이면, $i$번째 지점 $(X_i, Y_i)$에는 바위가 있다. 이를 한 번 채굴하면 바위를 얻으며, 이를 처분하는 비용은 $C_i = -W_i$이다.

  $W_i \neq 0$을 만족한다.

출력

표준 출력에 한 줄을 출력한다. 출력에는 JOI 왕국의 최대 이익이 포함되어야 한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

• $1 \le N \le 2\,000$.
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le |W_i| \le 1\,000\,000\,000$.
• $(X_i, Y_i) \neq (X_j, Y_j)$ ($1 \le i < j \le N$).

서브태스크

총 5개의 서브태스크가 있다. 각 서브태스크의 점수와 추가 제한은 다음과 같다:

서브태스크 1 [5점]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). 다시 말해, 모든 지점은 $x$축 위에 놓여 있다.

서브태스크 2 [20점]

• $N \le 100$.
• 서로 다른 세 지점이 한 직선 위에 놓이지 않는다.
• $L$을 서로 다른 두 지점을 지나는 $xy$ 평면 위의 직선이라 하자. $L'$을 서로 다른 두 지점을 지나는, $L$과는 다른 $xy$ 평면 위의 또 다른 직선이라 하자. 이때 $L$과 $L'$은 서로 평행하지 않다.

서브태스크 3 [35점]

• 서로 다른 세 지점이 한 직선 위에 놓이지 않는다.
• $L$을 서로 다른 두 지점을 지나는 $xy$ 평면 위의 직선이라 하자. $L'$을 서로 다른 두 지점을 지나는, $L$과는 다른 $xy$ 평면 위의 또 다른 직선이라 하자. 이때 $L$과 $L'$은 서로 평행하지 않다.

서브태스크 4 [20점]

• 서로 다른 세 지점이 한 직선 위에 놓이지 않는다.

서브태스크 5 [20점]

추가 제한이 없다.

예제

입력 1

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

출력 1

19

참고

예제 입력 1에서 JOI 왕국에 있는 금(Gold)과 바위(Rock)의 위치는 다음과 같다.

이 예제 입력에서는 지점 $2, 3, 4, 5$에서 금이나 바위를 채취할 수 있다. 그러면 JOI 왕국의 이익은 $19$가 된다. 이것이 JOI 왕국의 최대 이익이다.

입력 2

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

출력 2

15

참고

예제 입력 2에서는 지점 $1, 2, 3$이 한 직선 위에 있다. 또한 지점 $4, 5, 6$도 한 직선 위에 있다.

입력 3

5
0 0 2
4 0 2
3 2 -1
1 2 2
1 1 -1

출력 3

5

참고

예제 입력 3에서는 서로 다른 세 지점이 한 직선 위에 놓이지 않는다. 지점 $1$과 $2$를 지나는 직선을 $L$이라 하고, 지점 $3$과 $4$를 지나는 직선을 $L'$이라 하자. 그러면 $L$과 $L'$은 서로 평행하다.

입력 4

2
0 0 -1
1 0 -1

출력 4

0

참고

금이나 바위가 전혀 없는 영역을 선택하는 것도 가능하다. 예제 입력 4에서 최대 이익은 $0$이다.

입력 5

15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13

출력 5

107