Haybale Restacking

Interview

Time limit1sMemory limit128 MB

Summary

Given N piles in a circle with current and target amounts of hay, move bales at cost equal to circular distance to reach the target with minimum total work.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, Math, Array
Solved: No attempts yet

Problem

Farmer John has just ordered a large number of hay bales. He wants to organize them into $N$ piles ( $1 \le N \le 100{,}000$ ) arranged in a circle, where pile $i$ should contain $B_i$ bales of hay. Unfortunately, the delivery driver only remembered to leave the hay in $N$ piles arranged in a circle. After delivery, pile $i$ contains $A_i$ bales of hay. Of course, the sum of the $A_i$ equals the sum of the $B_i$ .

Farmer John would like to move the bales from their current configuration (the $A_i$ ) into his target configuration (the $B_i$ ). Moving one bale from one pile to a pile that is $x$ steps away around the circle costs $x$ units of work. Compute the minimum total amount of work he needs.

Input

Line 1: the integer $N$ .
Lines 2 to $N+1$ : line $i+1$ contains two integers $A_i$ and $B_i$ ( $1 \le A_i, B_i \le 1000$ ).

Output

Print a single integer: the minimum total units of work Farmer John needs.

Hint

In the first example there are 4 piles around a circle initially holding 7, 3, 9, and 1 bales, with target amounts 1, 4, 2, and 13. A minimum of 13 units of work suffices: move 6 bales from pile 1 to pile 4, move 1 bale from pile 3 to pile 2, and move 6 bales from pile 3 to pile 4. Because the piles form a circle, pile 1 and pile 4 are adjacent, so each of those moves costs just 1 step per bale.

Examples6

Example 1
Input
```
4
7 1
3 4
9 2
1 13
```
Expected output
```
13
```
Example 2
Input
```
1
5 5
```
Expected output
```
0
```
Example 3
Input
```
2
3 3
4 4
```
Expected output
```
0
```
Example 4
Input
```
2
5 1
1 5
```
Expected output
```
4
```
Example 5
Input
```
3
10 1
1 1
1 10
```
Expected output
```
9
```
Example 6
Input
```
5
4 2
2 5
6 1
1 4
2 3
```
Expected output
```
7
```