Farmer John은 많은 건초를 주문해 원형의 $N$개 더미($1 \le N \le 100,000$)로 놓고 더미 $i$에 $B_{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$단위: 더미 $1$에서 $4$로 $6$개, $3$에서 $2$로 $1$개, $3$에서 $4$로 $6$개를 옮깁니다.

문제 출제자: Brian Dean, 2012