탑 쌓기

면접 대비

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

요약

각각 정사각형 밑면의 너비와 높이를 가진 N개의 블록이 주어질 때, 위로 갈수록 너비는 엄격히 줄고 높이는 줄지 않도록 블록을 쌓아 타워 높이의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 정렬, 이분 탐색, 배열
정답자: 아직 제출이 없습니다

문제

릴레 디르크 레프는 자신이 가진 $N$ 개의 블록으로 최대한 높은 탑을 쌓으려고 한다. 모든 블록은 밑면이 정사각형인 직육면체이고, 탑은 블록들을 곧바로 위로 쌓아 올린 집합이다. 블록 두 개가 나란히 놓여서는 안 된다. 탑이 불안정해져 무너지지 않으려면 각 블록의 너비, 즉 블록이 딛고 있는 정사각형 밑면의 한 변은 항상 그 블록이 딛고 있는 블록의 너비보다 엄격히 작아야 한다. 따라서 탑은 가장 넓은 블록을 맨 아래에 두고, 위로 갈수록 좁은 블록을 쌓아 올린다. 또한 탑이 예쁘게 보이려면 각 블록의 높이가 아래에 있는 블록의 높이 이상이어야 한다. 디르크가 최대한 얼마나 높은 탑을 쌓을 수 있는지 구해 주자.

입력

첫째 줄에는 디르크가 가진 블록의 수를 나타내는 정수 $N$ 이 주어진다. 이어서 $N$ 개의 줄이 주어지는데, 각 줄은 블록 하나에 해당한다. 이 중 $i$ 번째 줄에는 $i$ 번째 블록의 너비 $W_i$ 와 높이 $H_i$ 를 나타내는 두 정수가 주어진다. $1 \le W_i \le 10^9$ , $1 \le H_i \le 10^9$ 이다.

출력

디르크가 쌓을 수 있는 최대 높이를 정수 하나로 출력한다.

제한

$1 \le N \le 10^5$

예제3

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

예제 2

입력

예상 출력

예제 3
입력
```
3
1 2
1 2
1 3
```
예상 출력
```
3
```