Score: 500 points
New AtCoder City has an infinite grid of streets, as follows:
There are N residential areas in New AtCoder City. The i-th area is located at the intersection with the coordinates (X_i, Y_i) and has a population of P_i. Each citizen in the city lives in one of these areas.
The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.
M-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose K streets and build a railroad stretching infinitely along each of those streets.
Let the walking distance of each citizen be the distance from his/her residential area to the nearest railroad.
M-kun wants to build railroads so that the sum of the walking distances of all citizens, S, is minimized.
For each K = 0, 1, 2, \dots, N, what is the minimum possible value of S after building railroads?
Input is given from Standard Input in the following format:
N X_1 Y_1 P_1 X_2 Y_2 P_2 : : : X_N Y_N P_N
Print the answer in N+1 lines.
The i-th line (i = 1, \ldots, N+1) should contain the minimum possible value of S after building railroads for the case K = i-1.
3 1 2 300 3 3 600 1 4 800
2900 900 0 0
When K = 0, the residents of Area 1, 2, and 3 have to walk the distances of 1, 3, and 1, respectively, to reach a railroad.
Thus, the sum of the walking distances of all citizens, S, is 1 \times 300 + 3 \times 600 + 1 \times 800 = 2900.
When K = 1, if we build a railroad along the street corresponding to the line y = 4 in the coordinate plane, the walking distances of the citizens of Area 1, 2, and 3 become 1, 1, and 0, respectively.
Then, S = 1 \times 300 + 1 \times 600 + 0 \times 800 = 900.
We have many other options for where we build the railroad, but none of them makes S less than 900.
When K = 2, if we build a railroad along the street corresponding to the lines x = 1 and x = 3 in the coordinate plane, all citizens can reach a railroad with the walking distance of 0, so S = 0. We can also have S = 0 when K = 3.
The figure below shows the optimal way to build railroads for the cases K = 0, 1, 2.
The street painted blue represents the roads along which we build railroads.
5 3 5 400 5 3 700 5 5 1000 5 7 700 7 5 400
13800 1600 0 0 0 0
The figure below shows the optimal way to build railroads for the cases K = 1, 2.
6 2 5 1000 5 2 1100 5 5 1700 -2 -5 900 -5 -2 600 -5 -5 2200
26700 13900 3200 1200 0 0 0
The figure below shows the optimal way to build railroads for the case K = 3.
8 2 2 286017 3 1 262355 2 -2 213815 1 -3 224435 -2 -2 136860 -3 -1 239338 -2 2 217647 -1 3 141903
2576709 1569381 868031 605676 366338 141903 0 0 0
The figure below shows the optimal way to build railroads for the case K = 4.