시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3 3 3 100.000%

문제

JOI Kingdom is famous for producing gold. In JOI Kingdom, once in every year, they use a bulldozer to mine gold.

The land of JOI Kingdom is described as a plane with xy-coordinates. There are N spots in the land. The i-th spot (1 ≤ i ≤ N) is (Xi, Yi). Each spot has either gold or rock, but not both.

If the spot i has gold, when we mine it once, we obtain gold of value Vi. If the spot i has rock, when we mine it once, we obtain rock. The cost to discard it is Ci.

We use a bulldozer for mining in the following way. First, we choose two parallel lines in the xy-plane. Then, we mine all gold and rock, once for each, in the area between two parallel lines (including gold or rock lying on them).

The profit of JOI Kingdom is the total value of gold in the area for mining minus the total cost to discard rock in the same area. We want to maximize the profit of JOI Kingdom.

Write a program which calculates the maximum profit of JOI Kingdom.

입력

Read the following data from the standard input.

  • The first line of input contains an integer N, the number of spots where we can take gold or rock.
  • The i-th line (1 ≤ i ≤ N) of the following N lines contains three space separated integers Xi, Yi, Wi.
    • If Wi ≥ 1, the i-th spot (Xi, Yi) has gold. When we mine it once, we obtain gold of value Vi = Wi.
    • If Wi ≤ −1, the i-th spot (Xi, Yi) has rock. When we mine it once, we obtain rock, and the cost to discard it is Ci = −Wi.
    • Wi ≠ 0 is satisfied.

출력

Write one line to the standard output. The output contains the maximum profit of JOI Kingdom.

제한

All input data satisfy the following conditions.

  • 1 ≤ N ≤ 2 000.
  • −1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • −1 000 000 000 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ |Wi| ≤ 1 000 000 000.
  • (Xi, Yi) , (Xj, Yj) (1 ≤ i < j ≤ N).

서브태스크 1 (5점)

  • N ≤ 100.
  • Yi = 0 (1 ≤ i ≤ N). In other words, all spots lie on the x-axis.

서브태스크 2 (20점)

  • N ≤ 100.
  • No three distinct spots lie on a line.
  • Let L be a line on the xy-plane passing through two distinct spots. Let L′ be another line, different from L, on the xy-plane passing through two distinct spots. Then, L and L′ are not parallel to each other.

서브태스크 3 (35점)

  • No three distinct spots lie on a line.
  • Let L be a line on the xy-plane passing through two distinct spots. Let L′ be another line, different from L, on the xy-plane passing through two distinct spots. Then, L and L′ are not parallel to each other.

서브태스크 4 (20점)

  • No three distinct spots lie on a line.

서브태스크 5 (20점)

There are no additional constraints.

예제 입력 1

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

예제 출력 1

19

In Sample Input 1, the positions of gold and rock in JOI Kingdom are as follows.

In this sample input, we can take gold or rock at the spots 2, 3, 4, 5. Then the profit of JOI Kingdom is 19. This is the maximum profit of JOI Kingdom.

예제 입력 2

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

예제 출력 2

15

In Sample Input 2, the spots 1, 2, 3 lie on a line. Also, the spots 4, 5, 6 lie on a line.

예제 입력 3

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

예제 출력 3

5

In Sample Input 3, no three distinct spots lie on a line. Let L be a line passing through the spots 1 and 2, and let L′ be a line passing through the spots 3 and 4. Then, L and L′ are parallel to each other.

예제 입력 4

2
0 0 -1
1 0 -1

예제 출력 4

0

It is possible to choose the area without any gold or rock. In Sample Input 4, the maximum profit is 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

채점

  • 예제는 채점하지 않는다.