Farmer John pidió muchos fardos y quiere $N$ montones en círculo ($1 \le N \le 100,000$), con $B_{i}$ fardos en el montón $i$. El conductor no escuchó bien y solo recordó los $N$ montones en círculo. Tras la entrega, el montón $i$ tiene $A_{i}$ fardos. Las sumas de $A_{i}$ y $B_{i}$ son iguales.

Quiere pasar de la configuración $A_{i}$ a la deseada $B_{i}$. Mover un fardo a un montón a $x$ pasos por el círculo cuesta $x$ unidades de trabajo. Halla el mínimo.

Entrada

• Línea $1$: entero $N$.

• Líneas $2..1+N$: la línea $i+1$ contiene $A_{i}$ y $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Salida

Ejemplos

Entrada 1

4
7 1
3 4
9 2
1 13

Salida 1

13

Nota

Hay $4$ montones de $7$, $3$, $9$, $1$ fardos; la meta es $1$, $4$, $2$, $13$.

Se necesitan como mínimo $13$ unidades: mover $6$ fardos del montón $1$ al $4$, $1$ del $3$ al $2$ y $6$ del $3$ al $4$.

Autor del problema: Brian Dean, 2012