$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$. לאחרות סיכון נמוך יותר.