17559번 - Paris by Night 다국어

During her trip to Paris for SWERC, Morgane graded every monument she visited. On this last night of the week, she plans to go in some hot-air balloon and take two 180° panoramic photographs of the city, thereby getting a perfect 360° view. She would like both photographs to be approximately as nice as each other.

Hence, she will proceed as follows. She chooses two monuments, that we will call the boundary monuments, and asks the balloon pilot to go between these monuments. From there, she takes two 180° pictures: each picture shows one side of Paris, both sides being delimited by the two boundary monuments. Each picture receives a grade, which is the sum of the grades of the monuments that it shows, including the boundary monuments on both pictures. Finally, if the pictures have grades A and B, the goal of Morgane is to minimize the difference between A and B (in absolute value).

The visibility from the balloon is such that all monuments can be seen in either of the two photographs.

You must assist Morgane in choosing appropriate boundary monuments. In order to do this, you are given a list of the monuments. For every monument visited by Morgane, this list contains a line which indicates the Cartesian coordinates of the monument location, along with the monument’s grade. You should give the minimal possible difference, among all pairs of pictures that Morgane may take, between the grades of the two pictures.

The input comprises several lines, each consisting of integers separated with single spaces:

• the first line contains the number N of monuments;
• each of the N next lines contains three integers associated with each monument: the X coordinate, the Y coordinate and the grade G of the monument represented on that line.

The output should consist of a single line, whose content is an integer, the minimal difference (in absolute value) between the grades of a pair of photographs that Morgane may take.

• 2 ≤ N ≤ 4 000;
• 0 ≤ X,Y ≤ 1 000 000 000 and 1 ≤ G ≤ 1 000 000 000.

Morgane was so precise at locating every monument that no three monuments are on a same straight line.