eolymp
bolt
Try our new interface for solving problems
Məsələlər

Отрезки

Отрезки

Zaman məhdudiyyəti 0.2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть N прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер i характеризуется двумя числами — длиной L_i и ценой C_i. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

Напишите программу, которая по информации об отрезках найдет наименьшую стоимость трех отрезков, из которых мальчик может сложить треугольник, либо определит, что это сделать невозможно.

Giriş verilənləri

В первой строке входного файла записано единственное число N— количество отрезков. В следующих N строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие L_i (1 ≤ L_i ≤ 10^9) и С_i. Цены образуют перестановку чисел от 1 до N, то есть являются попарно различными натуральными числами, не превосходящими N.

Çıxış verilənləri

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Nümunə

Giriş verilənləri #1
4
1 1
2 2
3 3
4 4
Çıxış verilənləri #1
9

Qiymətləndirmə

Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:

  1. 20 баллов: 1 ≤ N ≤ 100

  2. 20 баллов: 100 < N ≤ 3000

  3. 30 баллов: 3000 < N ≤ 10 000

  4. 30 баллов: 10 000 < N ≤ 100 000

Müəllif Роман Рубаненко, Роман Фурко
Mənbə XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск