Bulldozer
Time limit2sMemory limit512 MB
Choose two parallel lines and take every weighted point between them, maximizing the sum of gold values minus rock costs.
- Level
Hard8 of 10
- Topics
- Geometry, Sorting, Dynamic programming, Brute force
- Solved
- No attempts yet
Problem
JOI Kingdom is famous for producing gold. In JOI Kingdom, once every year, a bulldozer is used 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 spot i has gold, mining it once yields gold of value Vi. If spot i has rock, mining it once yields rock, and the cost to discard it is Ci.
A bulldozer is used for mining in the following way. First, choose two parallel lines in the xy-plane. Then, mine all gold and rock, once each, in the area between the two parallel lines (including gold or rock lying on them).
The profit of JOI Kingdom is the total value of gold in the mined area minus the total cost to discard rock in the same area. We want to maximize the profit of JOI Kingdom.
Write a program that calculates the maximum profit of JOI Kingdom.
Input
Read the following data from standard input.
-
The first line of input contains an integer N, the number of spots where gold or rock can be taken.
-
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. Mining it once yields gold of value Vi = Wi.
- If Wi ≤ −1, the i-th spot (Xi, Yi) has rock. Mining it once yields rock, and the cost to discard it is Ci = −Wi.
- Wi ≠ 0 holds.
Output
Write one line to standard output. The output contains the maximum profit of JOI Kingdom.
Constraints
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).