건초 더미 재배치

농부 John이 많은 건초 더미를 주문했다. 그는 이 건초를 원형으로 배치된 $N$개의 더미($1 \le N \le 100{,}000$)로 정리하려고 하며, $i$번 더미에는 $B_i$개의 건초가 있어야 한다. 그런데 배달 기사는 건초를 원형으로 배치된 $N$개의 더미로 내려놓아야 한다는 것만 기억했다. 배달이 끝난 뒤 $i$번 더미에는 $A_i$개의 건초가 있다. 물론 $A_i$의 총합과 $B_i$의 총합은 서로 같다.

John은 현재 배치($A_i$)를 원하는 목표 배치($B_i$)로 바꾸려고 한다. 건초 한 개를 원을 따라 $x$칸 떨어진 더미로 옮기는 데는 $x$만큼의 작업량이 든다. 필요한 최소 작업량을 구하여라.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 두 정수 $A_i$와 $B_i$가 주어진다 ($1 \le A_i, B_i \le 1000$).

John이 필요로 하는 최소 작업량을 정수 하나로 출력한다.

첫 번째 예시에서는 원형으로 배치된 4개의 더미가 처음에 각각 7, 3, 9, 1개의 건초를 가지고 있고, 목표는 1, 4, 2, 13개이다. 최소 13의 작업량이면 충분하다: 1번 더미에서 4번 더미로 6개, 3번 더미에서 2번 더미로 1개, 3번 더미에서 4번 더미로 6개를 옮긴다. 더미가 원을 이루므로 1번 더미와 4번 더미는 서로 인접하며, 따라서 이 이동들은 건초 한 개당 1칸씩만 든다.