Farmer John a commandé beaucoup de balles et souhaite $N$ piles en cercle ($1 \le N \le 100,000$), avec $B_{i}$ balles dans la pile $i$. Le livreur n'a pas bien écouté et n'a retenu que les $N$ piles en cercle. Après livraison, la pile $i$ contient $A_{i}$ balles. Les sommes des $A_{i}$ et $B_{i}$ sont bien sûr identiques.

Il veut passer de la configuration $A_{i}$ à la cible $B_{i}$. Déplacer une balle vers une pile distante de $x$ pas autour du cercle coûte $x$ unités de travail. Trouvez le travail minimal.

Entrée

• Ligne $1$ : entier $N$.

• Lignes $2..1+N$ : la ligne $i+1$ contient $A_{i}$ et $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Sortie

Exemples

Entrée 1

4
7 1
3 4
9 2
1 13

Sortie 1

13

Remarque

Il y a $4$ piles de $7$, $3$, $9$, $1$ balles ; la cible est $1$, $4$, $2$, $13$.

Le minimum est $13$ unités : déplacer $6$ balles de la pile $1$ à $4$, $1$ de $3$ à $2$ et $6$ de $3$ à $4$.

Auteur du problème : Brian Dean, 2012