У пари

Фермер Джон виявив, що корову легше доїти, якщо поряд є інша корова для моральної підтримки. Тому він хоче розбити m своїх корів (m ≤ 10^9, m парне) на m / 2 пар. Кожну з цих пар він розміщує в окремому стійлі, і всі пари корів дояться одночасно.

Кожна з корів дає різну кількість молока. Якщо корови в парі дають по a і b літрів молока, то для доїння цієї пари потрібно a + b одиниць часу.

Допоможіть ФД визначити мінімально можливу кількість часу на весь процес доїння, за умови, що корови розбиті на пари найкращим чином.

Вхідні дані

Перший рядок містить n (1 ≤ n ≤ 10^5). Кожен з наступних n рядків містить два цілих числа x і y, що вказують, що у ФД є x корів з виробництвом молока по y (1 ≤ y ≤ 10^9) літрів. Сума всіх x-ів є m - загальна кількість корів.

Вихідні дані

Виведіть мінімальну кількість часу, яку займе доїння всіх корів, за умови, що вони розбиті на пари оптимальним чином.

Приклади

Примітка

Наприклад, якщо спарувати корови з продуктивністю 8 і 2, а також 5 і 5, то обидві пари можна буде подоїти, витративши 10 одиниць часу на доїння кожної пари. Оскільки доїння всіх пар йде паралельно, то весь процес завершиться через 10 одиниць часу. Будь-яке інше розбиття на пари дасть результат більше 10.