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

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

1 seconde
256 mégaoctets
Medium

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

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

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

Input

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

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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