화장지 롤

면접 대비

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

요약

모든 두루마리의 풀린 길이를 각 전체 길이를 넘지 않는 같은 값으로 맞추는 최소 이동 횟수를 구합니다.

난이도: 보통10점 중 5점
유형: 정렬, 수학
정답자: 아직 제출이 없습니다

문제

화장실에 두루마리 휴지 $n$ 개가 있습니다. $i$ 번째 휴지는 전체 길이 $d_i$ 와 현재 풀려 있는 길이 $r_i$ 를 가지며, 풀린 길이는 전체 길이를 넘을 수 없습니다(즉 $0 \le r_i \le d_i$ ).

한 번의 동작으로 임의의 휴지 하나를 정확히 1 cm 감거나 풀 수 있습니다. 다시 말해 한 동작은 어떤 $r_i$ 를 $1$ 만큼 늘리거나 줄이며, 이때도 항상 $0 \le r_i \le d_i$ 가 유지되어야 합니다. 모든 휴지의 풀린 길이가 같아지도록 만들 때 필요한 최소 동작 수를 구하세요.

입력

첫째 줄에 휴지의 개수 $n$ ( $1 \le n \le 10^6$ )이 주어집니다. 이어지는 $n$ 개의 줄에는 각 휴지의 정보가 두 정수 $d_i$ 와 $r_i$ 로 주어지며, 각각 $i$ 번째 휴지의 전체 길이와 풀린 길이를 의미합니다 ( $0 \le r_i \le d_i \le 10^9$ ).

출력

모든 휴지의 풀린 길이를 같게 만들기 위한 최소 동작 수를 한 줄에 출력하세요.

예제2

예제 1
입력
```
3
50 10
40 20
30 30
```
예상 출력
```
20
```
예제 2
입력
```
1
10 5
```
예상 출력
```
0
```