시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 76 37 26 53.061%

문제

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

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

입력

첫째 줄에 블록의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 블록의 정보 Wi, Di (1 ≤ Wi, Di ≤ 1,000,000,000)가 한 줄에 하나씩 1번 블록부터 순서대로 주어진다.

출력

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

예제 입력 1

5
4 2
4 6
4 5
3 1
3 3

예제 출력 1

3

예제 입력 2

5
4 2
3 1
3 3
4 5
4 6

예제 출력 2

5

출처