У пари#10524

У пари

1 секунда

128 мегабайтів

Середня

Фермер Джон виявив, що його корів легше доїти, коли поруч знаходиться інша корова, яка надає моральну підтримку. Тому він хоче взяти своїх $m$ корів ( $m \leq 1 0^{9}$ m \le 10^9, $m$ — парне число) і розбити їх на $m /2$ пар. Потім кожну пару корів відведуть до окремого стійла в корівнику для доїння. Доїння в усіх $m /2$ стійлах відбуватиметься одночасно.

Щоб трохи ускладнити задачу, кожна корова Фермера Джона дає різну кількість молока. Якщо в пару об'єднати корів з надоями $a$ і $b$ , то на їхнє доїння разом знадобиться $a + b$ a + b одиниць часу.

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

Вхідні дані

У першому рядку міститься $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). У кожному з наступних $n$ рядків містяться два цілих числа $x$ і $y$ , що означають, що у Фермера Джона є $x$ корів, кожна з яких дає $y (1 \leq y \leq 1 0^{9})$ y~(1 \le y \le 10^9) одиниць молока. Сума всіх $x$ дорівнює $m$ , загальній кількості корів. Гарантується, що $m$ — парне число.

Вихідні дані

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

Приклади

Припустимо, наприклад, що корови з надоями $8$ і $2$ об'єднані в одну пару, а дві корови з надоєм $5$ — в іншу. Тоді доїння в кожному з двох стійл займе $10$ одиниць часу. Оскільки доїння в усіх стійлах відбувається одночасно, весь процес завершиться через $10$ одиниць часу.

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

Приклад 1