Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить m своих коров (m ≤ 109, m чётное) на m / 2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по a и b литров молока, то для дойки этой пары требуется a + b единиц времени.

Помогите ФД определить минимально возможное количество времени на весь процесс дойки, в предположении, что коровы разбиты на пары наилучшим образом.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 105). Каждая из следующих n строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 ≤ y ≤ 109) литров. Сумма всех x-ов есть m - общее количество коров.

Выходные данные

Выведите минимальное количество времени, которое займёт дойка всех коров, в предположении, что они разбиты на пары оптимальным образом.

Пояснение

Здесь если спаровать коровы с производительностью 8 и 2, а также 5 и 5, то обе пары можно будет подоить, потратив 10 единиц времени на дойку каждой пары. Поскольку дойка всех пар идёт параллельно, то весь процесс завершится через 10 единиц времени. Любое другое разбиение на пары даст результат больше 10.