|
Відрізки (Роман Рубаненко, Роман Фурко)
Умова
Петрик дуже любить іграшки у формі геометричних фігур. Нещодавно він помітив, що серед його іграшок немає жодного трикутника. Це дуже засмутило Петрика, тому він пішов до найближчого магазину, щоб придбати новісінький трикутник. В магазині Петрику сказали, що всі трикутники вже давно розкупили, але в наявності є N прямих відрізків.
Відрізки пронумеровані послідовними натуральними числами, починаючи з одиниці. Відрізок номер i характеризується двома числами — довжиною Li та ціною Ci. Петрик дуже розумний, тому знає, що бажаний трикутник він може скласти з трьох відрізків. Більше того, наш герой знає, що трикутник можливо скласти лише з таких відрізків, що довжина будь-якого з них має бути строго меншою за сумарну довжину інших двох. Отже, хлопчик вирішив придбати рівно три таких відрізки. Звичайно, він хоче заощадити якомога більше коштів на морозиво, тому хоче витратити якнайменше на покупку відрізків для свого трикутника.
Завдання. Напишіть програму segments, яка за інформацією про відрізки визначить мінімальну вартість трьох відрізків, з яких хлопчик зможе скласти трикутник, або визначить, що це зробити неможливо.
Вхідні дані. В першому рядку вхідного файла segments.dat записано єдине число N — кількість відрізків. Далі в N рядках записана інформація про самі відрізки. Кожен такий рядок містить відповідні Li (1<=Li<= 109) та Сi.Ціни утворюють перестановку чисел від 1 до N, тобто є попарно різними натуральними числами, не більшими за N.
Вихідні дані. Вихідний файл segments.sol має містити єдине число — мінімальну вартість трьох відрізків, з яких можна скласти трикутник, або «−1» (лапки для наочності) в тому
випадку, якщо вибрати рівно три такі відрізки неможливо.
Оцінювання. Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:
o 20 балів: 1 <=N<= 100.
o 20 балів: 100 <=N<= 3000.
o 30 балів: 3000 <=N<= 104.
o 30 балів: 104 <=N<=105.
Приклади вхідних та вихідних даних.
segments.dat
4
1 1
2 2
3 3
4 4
segments.sol
9
segments.dat
3
3 1
5 3
10 2
segments.sol
-1
|
