Ілля ремонтує Пассат

Ілля, головний менеджер по рекламі Сергія, дуже любить свій автомобіль — Volkswagen Passat 2008 року випуску (Пассат). Але він дуже часто ламається, та ось знову зламався двигун.

Щоб полагодити Пассат, Ілля повинен заробити грошей. Оскільки він є менеджером по рекламі Сергія, він може планувати розміщення реклами в інстаграмі Сергія та отримувати з цього процент. В один день в інстаграмі можна розмістити тільки одну рекламу. В Іллі вже є $n$ замовлень на рекламу, кожне з яких характеризується двома цілими числами: $t_i$ — кількість днів, коли треба розміщувати рекламу з цього замовлення, та $d_i$ — день, до якого треба встигнути розмістити цю рекламу $t_i$ разів. Ілля не зобов'язаний показувати всю рекламу для одного рекламодавця в послідовні дні.

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

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) "— кількість замовлень на рекламу.

Кожен з наступних $n$ рядків містить по два цілі числа $t_i$ та $d_i$ ($1\le t_i,d_i\le 10^9$) "— кількість днів, скільки потрібно розміщувати $i$-ту рекламу, та останній можливий день розміщення цієї реклами.

Output

Виведіть одне ціле число — відповідь на завдання.

Examples

Note

У першому прикладі є чотири замовлення на рекламу. Ілля може спочатку $2$ дні нічого не робити, а потім на $3$-ій день виконати перше замовлення в останній можливий день. Далі є вибір. Або відразу виконати друге замовлення за $4$-ий день, а потім $9$ днів підряд від $5$-го до $13$-го розміщувати четверту рекламу. Або можна, наприклад, від $4$-го до $9$-го дня виконувати четверте замовлення, після чого $10$-го дня виконати друге замовлення, і далі до $13$-го дня продовжити виконувати четверте замовлення. Після цього від $14$-го до $100$-го дня він може розміщувати третю рекламу в будь-які $50$ днів.