Farmer John заказал много тюков сена и хотел $N$ куч по кругу ($1 \le N \le 100,000$), с $B_{i}$ тюками в куче $i$. Водитель слушал невнимательно и запомнил лишь $N$ куч по кругу. После доставки куча $i$ содержит $A_{i}$ тюков. Конечно, суммы $A_{i}$ и $B_{i}$ одинаковы.

Нужно перейти от текущих $A_{i}$ к желаемым $B_{i}$. Перенос одного тюка в кучу на $x$ шагов по кругу требует $x$ единиц работы. Найдите минимум работы.

Входные данные

• Строка $1$: целое $N$.

• Строки $2..1+N$: строка $i+1$ содержит целые $A_{i}$ и $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Выходные данные

Примеры

Входные данные 1

4
7 1
3 4
9 2
1 13

Выходные данные 1

13

Примечание

Есть $4$ кучи с $7$, $3$, $9$, $1$ тюками; цель — $1$, $4$, $2$, $13$.

Минимум $13$ единиц работы: перенести $6$ тюков из кучи $1$ в $4$, $1$ из $3$ в $2$, $6$ из $3$ в $4$.

Автор задачи: Brian Dean, 2012