Segments#7254
Petryk has a fondness for toys shaped like geometric figures. Recently, he realized that none of his toys are triangles, which made him quite upset. Determined to add a triangle to his collection, he visited the nearest store. Unfortunately, he found out that all the triangles were sold out, but there are straight segments available.
These segments are labeled with consecutive natural numbers starting from one. Each segment is defined by two numbers: its length L_i and its price C_i. Petryk, being clever, knows that he can create a triangle using three segments. He also understands that a valid triangle can only be formed if the length of any one segment is strictly less than the sum of the lengths of the other two segments. Therefore, Petryk plans to purchase exactly three such segments. Naturally, he wants to save as much money as possible for ice cream, so he aims to minimize the cost of these segments.
Write a program that determines the minimum cost of three segments from which Petryk can form a triangle, based on the given segment information. If forming such a triangle is impossible, the program should indicate this.
The first line of the input contains a single number — the number of segments. The following lines provide details about each segment. Each line contains two numbers: L_i (1 \leq L_i \leq 10^9) and C_i. The prices are a permutation of numbers from to , meaning they are distinct natural numbers not exceeding .
The output should be a single number — the minimum cost of three segments that can form a triangle, or -1 (without quotes) if it is impossible to select exactly three such segments.
1-nji mysal
The test set is divided into 4 blocks, with the following additional conditions:
20 points: 1 \leq N \leq 100
20 points: 100 < N \leq 3000
30 points: 3000 < N \leq 10\,000
30 points: 10\,000 < N \leq 100\,000