Problem
Ghiaccio는 베니스의 거리를 걷고 싶어합니다. 그러나 오늘 그는 매우 짜증이 나서 걷기가 어렵습니다.
베니스는 관광객들 사이에서 꽤 인기 있는 도시이지만, 정확한 "Venezia" 대신 외국어로 "Venice"라고 부릅니다.
이것은 Ghiaccio를 매우 화나게 하지만 그는 산책 후에 분노를 유지하고 싶지 않습니다. 그래서 그는 다시는 화를 내지 않기 위해 관광객 옆을 지날 때 가끔 귀를 막겠다고 결심했다.
Ghiaccio에는 초당 1포인트씩 채워지는 내부 진정 막대가 있습니다(Ghiaccio가 집을 떠날 때 이 막대의 값은 0입니다).
그러나 Ghiaccio가 d명이 있는 관광객 그룹을 지나치면 그의 평온함은 d만큼 감소합니다. 그는 도시 이름의 잘못된 발음에 화를 낸다. 하지만 지아치오가 귀를 막고 지나가더라도 그의 평온함은 줄어들지 않을 것이다.
어느 시점에서 차분한 척도가 음수가 되면 Ghiaccio는 광포해지며 이는 매우 용납할 수 없는 일입니다.
Ghiaccio는 베니스를 매우 잘 알고 있으므로 산책하는 동안 약 n개의 관광 그룹을 지나갈 것이라는 것을 알고 있습니다. 그룹에는 d< sub>i명이 있을 것입니다.
이 정보를 바탕으로 Ghiaccio가 걷는 동안 광포하지 않도록 귀를 막아야 하는 최소 횟수를 계산하세요.
입력:
첫 번째 줄에는 단일 정수 n(1 ≤ n ≤ 200000)이 포함되어 있습니다. Ghiaccio가 지나갈 관광 그룹의 수.
그런 다음 각각 공백으로 구분된 두 개의 정수인 t
i 및 d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — Ghiaccio가 i 번째 관광객 그룹을 통과하는 초의 수와 그 안에 있는 사람들의 수. 모든 t
i는 고유하며 오름차순입니다.
출력:
단일 정수 인쇄 — Ghiaccio가 광포하지 않기 위해 귀를 막아야 하는 최소 횟수입니다.
예:
<몸>
| 입력 |
출력 |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
설명:
첫 번째 예에서 Ghiaccio는 두 번째 그룹 근처를 지나가는 동안 귀를 막아야 했습니다.
그런 다음 세 번째 초가 끝날 때까지 그의 평온함은 1이 될 것입니다(그는 걷는 매초마다 3을 보충했지만 첫 번째 그룹을 지나갈 때 2씩 감소했습니다).
5초가 끝날 때까지 평온함은 3이 됩니다(지나치오가 지나갈 때 귀를 막았기 때문에 평온함은 두 번째 그룹에서 감소하지 않습니다).
그리고 6초가 끝날 무렵 평온함은 3+1-3 = 1이 됩니다.
또한 그의 평온함은 결코 줄어들지 않습니다.