Farmer John הזמין הרבה חבילות ורוצה $N$ ערמות במעגל ($1 \le N \le 100,000$), עם $B_{i}$ חבילות בערמה $i$. הנהג לא הקשיב היטב וזכר רק $N$ ערמות במעגל. אחרי המשלוח בערמה $i$ יש $A_{i}$ חבילות. סכומי $A_{i}$ ו־$B_{i}$ שווים כמובן.

הוא רוצה לעבור מהסידור $A_{i}$ ליעד $B_{i}$. העברת חבילה לערמה במרחק $x$ צעדים במעגל עולה $x$ יחידות עבודה. מצאו את העבודה המזערית.

קלט

• שורה $1$: השלם $N$.

• שורות $2..1+N$: שורה $i+1$ מכילה $A_{i}$ ו־$B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

פלט

דוגמאות

קלט 1

4
7 1
3 4
9 2
1 13

פלט 1

13

Note

יש $4$ ערמות עם $7$, $3$, $9$, $1$ חבילות; היעד $1$, $4$, $2$, $13$.

המינימום $13$ יחידות: להעביר $6$ חבילות מערמה $1$ ל־$4$, $1$ מ־$3$ ל־$2$, ו־$6$ מ־$3$ ל־$4$.

מחבר הבעיה: Brian Dean, 2012