Маленький D готується до навколосвітньої подорожі. Перед відправленням йому потрібно за планом виконати $n$ операцій із підготовки припасів зі списку, які спочатку за порядком пронумеровані числами $1, 2, \dots, n$.

Позначимо поточну кількість припасів цілим числом $x$, спочатку $x = 0$. $i$-та операція описується двома додатними цілими числами $a_i, b_i$; під час виконання цієї операції послідовно відбуваються такі зміни:

1. Спочатку $x$ збільшується на $a_i$ (тобто присвоюється $x \leftarrow x + a_i$);
2. Потім перевіряється величина $x$: якщо в цей момент $x > b_i$, то $x$ зменшується до $b_i$ (тобто присвоюється $x \leftarrow \min(x, b_i)$).

Перед початком виконання операцій Маленький D може виконати не більше одного коригування порядку списку: вибрати довільну одну з операцій, вилучити її та перемістити в кінець послідовності, при цьому відносний порядок решти операцій залишається незмінним (також можна не робити жодних змін).

Після завершення коригування Маленький D послідовно виконає всі $n$ операцій у новому порядку від початку до кінця, кожну операцію рівно один раз. Маленький D хоче дізнатися, якою може бути максимально можлива кількість припасів $x$ після виконання всіх операцій?

Вхідні дані

Дані зчитуються зі stdin.

Перший рядок містить одне додатне ціле число $n$, що позначає кількість операцій.

У наступних $n$ рядках $i$-й рядок містить два додатні цілі числа $a_i, b_i$, які описують параметри $i$-ї операції.

Вихідні дані

Виведіть результат у stdout.

Виведіть один рядок, що містить одне ціле число — максимально можливе значення кількості припасів $x$ після виконання всіх операцій.

Приклади

Вхідні дані 1

3
1 100
100 90
1 1

Вихідні дані 1

90

Примітка

Якщо перемістити $2$-гу операцію в кінець послідовності, порядок виконання операцій стане $1, 3, 2$. Після виконання кожної операції значення $x$ послідовно стає рівним $1, 1, 90$.

Якщо перемістити $1$-шу операцію в кінець, у підсумку вийде $x = 2$; якщо не змінювати порядок або перемістити $3$-тю операцію в кінець, у підсумку вийде $x = 1$. Отже, максимально можливе значення $x$ дорівнює $90$.

Приклад 2

Див. файли supply/supply2.in та supply/supply2.ans у директорії учасника.

Цей приклад задовольняє обмеження тестів $1 \sim 4$.

Приклад 3

Див. файли supply/supply3.in та supply/supply3.ans у директорії учасника.

Цей приклад задовольняє обмеження тестів $5 \sim 6$.

Приклад 4

Див. файли supply/supply4.in та supply/supply4.ans у директорії учасника.

Цей приклад задовольняє обмеження тестів $7 \sim 10$.

Обмеження

Для всіх даних гарантується, що $1 \le n \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$. Зверніть увагу: дані не гарантують, що $a_i \le b_i$.

Усього в задачі $10$ тестів, кожен тест оцінюється в $10$ балів, усі тести оцінюються незалежно. Детальні обмеження наведено в таблиці нижче.

Особлива властивість A: $b_1 = b_2 = \dots = b_n$.