Farmer John encomendou muitos fardos e quer $N$ montes em círculo ($1 \le N \le 100,000$), com $B_{i}$ fardos no monte $i$. O motorista não ouviu bem e só recordou os $N$ montes em círculo. Após entrega, o monte $i$ tem $A_{i}$ fardos. As somas de $A_{i}$ e $B_{i}$ são iguais.

Quer passar da configuração $A_{i}$ para a desejada $B_{i}$. Mover um fardo para um monte a $x$ passos pelo círculo custa $x$ unidades de trabalho. Determine o mínimo.

Entrada

• Linha $1$: inteiro $N$.

• Linhas $2..1+N$: a linha $i+1$ contém $A_{i}$ e $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Saída

Exemplos

Entrada 1

4
7 1
3 4
9 2
1 13

Saída 1

13

Note

Há $4$ montes de $7$, $3$, $9$, $1$ fardos; o objetivo é $1$, $4$, $2$, $13$.

O mínimo é $13$ unidades: mover $6$ fardos do monte $1$ para $4$, $1$ de $3$ para $2$ e $6$ de $3$ para $4$.

Autor do problema: Brian Dean, 2012