Отрезки
Отрезки
Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть Nпрямых отрезков.
Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер iхарактеризуется двумя числами — длиной L_i и ценой C_i. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.
Задание
Напишите программу, которая по информации об отрезках найдет наименьшую стоимость трех отрезков, из которых мальчик может сложить треугольник, либо определит, что это сделать невозможно.
Входные данные
В первой строке входного файла записано единственное число N— количество отрезков. В следующих Nстроках записана информация о самих отрезках. Каждая такая строка содержит соответствующие L_i (1 ≤ L_i ≤ 10^9)и С_i. Цены образуют перестановку чисел от 1 до N, то есть являются попарно различными натуральными числами, не превосходящими N.
Выходные данные
Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.
Пример
4 1 1 2 2 3 3 4 4
9
Оценивание
Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:
20 баллов: 1 ≤ N ≤ 100
20 баллов: 100 < N ≤ 3000
30 баллов: 3000 < N ≤ 10 000
30 баллов: 10 000 < N ≤ 100 000