시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB1196100.000%

문제

Farmer Gumbauskas is growing potatoes. He planted potatoes in one long furrow and placed bags with fertilisers next to the furrow.

Assume that the furrow consists of $N$ segments of the same length. The segments are numbered from $1$ to $N$ from left to right. In segment $i$ there are $a_i$ fertilisers and were planted $b_i$ potatoes. One fertiliser unit is required to fertilise one planted potato. There is enough fertiliser for all the potatoes, i.e. $a_1 + \cdots + a_N ≥ b_1 + \cdots + b_N$.

However, it costs to transfer fertiliser from one segment to another. To transfer one unit of fertiliser from segment $i$ to segment $j$ costs $|i - j|$.

Find the cheapest way to fertilise all the potatoes.

입력

The length of the furrow $N$ is given in the first line.

Each of the remaining $N$ lines contain two integers $a_i$ and $b_i$ – the amount of fertiliser unit and the amount of potatoes planted in segment $i$. The segments are given in the increasing order of $i$.

출력

Output the smallest possible cost of fertilising all the planted potatoes.

제한

  • $1 ≤ N ≤ 500\,000$
  • $0 ≤ a_i , b_i ≤ 1\,000\,000$

서브태스크

Further the following notation will be used: $A = a_1 + \cdots + a_N$ and $B = b_1 + \cdots + b_N$.

번호배점제한
124

The same amount of fertiliser and potatoes: $A = B$

210

$A = B$ or $A = B + 1$

320

$N ≤ 3000$ and $A, B ≤ 30\,000$

410

$N ≤ 3000$

536

No additional constraints

예제 입력 1

6
1 2
0 0
2 0
0 0
0 0
0 1

예제 출력 1

5

The cheapest way to fertilise all the potatoes (fertiliser is indicated above the horizontal line, potatoes are below the line):

Adding the distances we get: $0 + 2 + 3 = 5$.

예제 입력 2

7
2 0
2 0
2 0
0 5
2 0
2 0
2 0

예제 출력 2

6

The fertiliser for four potatoes is transferred from neighbouring segments, while for the remaining potato it is delivered from further located segment.

채점 및 기타 정보

  • 예제는 채점하지 않는다.