Відрізки

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

Відрізки пронумеровані послідовними натуральними числами, починаючи з одиниці. Відрізок номер iхарактеризується двома числами — довжиною L_i та ціною C_i. Петрик дуже розумний, тому знає, що бажаний трикутник він може скласти з трьох відрізків. Більше того, наш герой знає, що трикутник можливо скласти лише з таких відрізків, що довжина будь-якого з них має бути строго меншою за сумарну довжину інших двох. Отже, хлопчик вирішив придбати рівно три таких відрізки. Звичайно, він хоче заощадити якомога більше коштів на морозиво, тому хоче витратити якнайменше на покупку відрізків для свого трикутника.

Завдання

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

Вхідні дані

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

Вихідні дані

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

Приклади

Оцінювання

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

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

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

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

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