Farmer John zamówił wiele bel i chce $N$ stosów w okręgu ($1 \le N \le 100,000$), z $B_{i}$ belami w stosie $i$. Kierowca nie słuchał uważnie i zapamiętał tylko $N$ stosów w okręgu. Po dostawie stos $i$ ma $A_{i}$ bel. Sumy $A_{i}$ i $B_{i}$ są oczywiście równe.

Chce przejść od obecnego układu $A_{i}$ do docelowego $B_{i}$. Przeniesienie beli do stosu oddalonego o $x$ kroków po okręgu wymaga $x$ jednostek pracy. Wyznacz minimum.

Wejście

• Wiersz $1$: całkowite $N$.

• Wiersze $2..1+N$: wiersz $i+1$ zawiera $A_{i}$ i $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Wyjście

Przykład

Wejście 1

4
7 1
3 4
9 2
1 13

Wyjście 1

13

Uwagi

Są $4$ stosy z $7$, $3$, $9$, $1$ belami; cel to $1$, $4$, $2$, $13$.

Minimum wynosi $13$ jednostek: przenieść $6$ bel ze stosu $1$ do $4$, $1$ z $3$ do $2$, i $6$ z $3$ do $4$.

Autor zadania: Brian Dean, 2012