Segments
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 N straight segments available.
These segments are labeled with consecutive natural numbers starting from one. Each segment i 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.
**Task**
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.
**Input**
The first line of the input contains a single number N — the number of segments. The following N lines provide details about each segment. Each line contains two numbers: L_i (1 ≤ L_i ≤ 10^9) and C_i. The prices are a permutation of numbers from 1 to N, meaning they are distinct natural numbers not exceeding N.
**Output**
The output should be a single number — the minimum cost of three segments that can form a triangle, or -1 if it is impossible to select exactly three such segments.
**Scoring**
The test set is divided into 4 blocks, with the following additional conditions:
1. 20 points: 1 ≤ N ≤ 100 2. 20 points: 100 < N ≤ 3000 3. 30 points: 3000 < N ≤ 10,000 4. 30 points: 10,000 < N ≤ 100,000