Farmer John ha ordinato molte balle e vuole $N$ pile in cerchio ($1 \le N \le 100,000$), con $B_{i}$ balle nella pila $i$. Il conducente ascoltava male e ha ricordato soltanto le $N$ pile in cerchio. Dopo la consegna, la pila $i$ ha $A_{i}$ balle. Le somme di $A_{i}$ e $B_{i}$ sono uguali.

Vuole passare dalla configurazione $A_{i}$ alla desiderata $B_{i}$. Spostare una balla a una pila distante $x$ passi sul cerchio costa $x$ unità di lavoro. Trova il minimo.

Input

• Riga $1$: intero $N$.

• Righe $2..1+N$: la riga $i+1$ contiene $A_{i}$ e $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Output

Esempi

Input 1

4
7 1
3 4
9 2
1 13

Output 1

13

Note

Ci sono $4$ pile con $7$, $3$, $9$, $1$ balle; l'obiettivo è $1$, $4$, $2$, $13$.

Il minimo è $13$ unità: spostare $6$ balle dalla pila $1$ alla $4$, $1$ dalla $3$ alla $2$ e $6$ dalla $3$ alla $4$.

Autore del problema: Brian Dean, 2012