Potatoes and fertilizers

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 구간에 비료와 감자가 있고, 인접 구간 사이에서 비료 한 단위를 옮기는 비용이 1일 때 모든 감자에 비료를 주는 최소 비용을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 누적 합, 배열, 수학
정답자: 아직 제출이 없습니다

문제

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$

예제2

예제 1
입력
```
6
1 2
0 0
2 0
0 0
0 0
0 1
```
예상 출력
```
5
```
예제 2
입력
```
7
2 0
2 0
2 0
0 5
2 0
2 0
2 0
```
예상 출력
```
6
```