Маленький 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$.