تخطط أبقار Farmer John وعددها $N$ ($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$. للأبقار الأخرى خطر أقل.