16783번 - Bulldozer 서브태스크다국어

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 (X_i, Y_i). 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 V_i. If the spot i has rock, when we mine it once, we obtain rock. The cost to discard it is C_i.

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 X_i, Y_i, W_i.
  • If W_i ≥ 1, the i-th spot (X_i, Y_i) has gold. When we mine it once, we obtain gold of value V_i = W_i.
  • If W_i ≤ −1, the i-th spot (X_i, Y_i) has rock. When we mine it once, we obtain rock, and the cost to discard it is C_i = −W_i.
  • W_i ≠ 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 ≤ X_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• −1 000 000 000 ≤ Y_i ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ |W_i| ≤ 1 000 000 000.
• (X_i, Y_i) ≠ (X_j, Y_j) (1 ≤ i < j ≤ N).

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

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

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

• No three distinct spots lie on a line.

There are no additional constraints.