$N$ коров Farmer John ($1 \le N \le 50{,}000$), с номерами $1..N$, хотят сбежать в цирк. Копыта мешают ходить по канату и качаться на трапеции (а последняя попытка выстрелить коровой из пушки провалилась). Поэтому они решили тренировать акробатику.

Они не слишком изобретательны и придумали лишь один трюк: стоять друг на друге вертикальной башней некоторой высоты. Теперь выбирают порядок в башне.

У каждой коровы вес ($1 \le W_i \le 10{,}000$) и сила ($1 \le S_i \le 1{,}000{,}000{,}000$). Риск падения равен суммарному весу коров выше неё (без её собственного) минус её сила, так что более сильная корова имеет меньший риск. Найдите порядок, минимизирующий наибольший риск среди коров.

Входные данные

• Строка 1: целое $N$.
• Строки $2..N+1$: строка $i+1$ описывает корову $i$ двумя целыми через пробел $W_i$ и $S_i$.

Выходные данные

• Строка 1: целое — наибольший риск всех коров в любом оптимальном порядке, минимизирующем риск.

Примеры

Входные данные 1

3
10 3
2 5
3 3

Выходные данные 1

2

Примечание

Поставьте корову веса 10 вниз. Она несёт двух других, поэтому риск равен $2+3-3=2$. У остальных риск меньше.