가로 블록 쌓기

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

요약

가로 블록 N개를 정해진 위치에 차례로 떨어뜨려 가장 높은 표면 위에 쌓고, 모든 블록을 놓은 뒤 스택의 높이를 구한다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 이분 탐색, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

가로 블록만 등장하는 테트리스 게임을 하려고 한다. 가로 블록은 총 $N$ 개가 등장할 예정이고, 등장하는 순서대로 $1, 2, \dots, N$ 번이다. $i$ 번 블록의 높이는 $1$ 이고, 너비는 $W_i$ 이다. $i$ 번 블록은 왼쪽 벽으로부터 거리가 $D_i$ 떨어진 곳에 떨어뜨려야 한다. 블록을 회전시키거나 위치를 이동시키는 것은 불가능하다.

블록은 위에서부터 떨어지며, 다른 블록 또는 바닥을 만날 때까지 한 칸씩 떨어진다. $N$ 개의 블록 정보가 주어졌을 때, 블록이 쌓인 높이를 구해보자.

입력

첫째 줄에 블록의 개수 $N$ ( $1 \le N \le 100{,}000$ )이 주어진다. 둘째 줄부터 $N$ 개의 줄에 블록의 정보 $W_i, D_i$ ( $1 \le W_i, D_i \le 1{,}000{,}000{,}000$ )가 한 줄에 하나씩 $1$ 번 블록부터 순서대로 주어진다.

출력

블록이 모두 쌓인 후 높이를 출력한다.

예제2

예제 1
입력
```
5
4 2
4 6
4 5
3 1
3 3
```
예상 출력
```
3
```
예제 2
입력
```
5
4 2
3 1
3 3
4 5
4 6
```
예상 출력
```
5
```