Однією з багатьох проблем технічної підготовки до виборів є друк бюлетенів. Щоб забезпечити належний ступінь захисту, всі бюлетені друкують на одному поліграфічному комбінаті. Оскільки на бюлетенях вказують номер округу, поліграфкомбінату доводиться мати справу з ~N~ різними замовленнями (де ~N~ – кількість округів); виконувати ці замовлення можна лише послідовно одне за одним; для бюлетенів кожного ~i~-го округу відомий час друкування ~t_{i,1}~.

Бюлетені на різні округи може відвозити різний транспорт. Причому, цього транспорту достатньо, щоб ні при якому порядку друку не виникало затримок, пов'язаних з його (транспорту) очікуванням. Тим не менш, перевезення бюлетенів кожного ~i~-го округу все ж займає значний час ~t_{i,2}~.

Момент остаточної готовності до виборів настає тоді, коли бюлетені вже доставлені в усі округи.

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

Вхідні дані

у першому рядку вказана кількість округів ~N~ (~2\leqslant N \leqslant 10^5~), наступні ~N~ рядків містять по два натуральні числа кожен – час друкування ~t_{i,1}~ та час доставки ~t_{i,2}~ бюлетенів відповідного округу. Усі значення ~t_{i,1}~ та ~t_{i,2}~ в межах ~2\leqslant t\leqslant 10^4~.

Результати

Єдине ціле число – знайдений мінімальний час від початку друкування до моменту остаточної готовності.

Приклади

Вхід

3
10 5
5 20
5 5

Результат

25

Вхід

4
10 5
5 12
25 8
12 6

Результат

57