탑 쌓기

Lille Dirk Ref는 자신이 가진 $N$개의 블록으로 가능한 한 높은 탑을 만들고 싶어 한다. 모든 블록은 밑면이 정사각형인 직육면체이며, 탑은 서로의 바로 위에 쌓인 블록들의 집합이다(두 블록을 서로 나란히 놓을 수는 없다). 탑이 불안정해져 무너지지 않으려면 각 블록의 너비(즉, 블록이 놓이는 정사각형 밑면의 변의 길이)는 그 블록이 올라가 있는 블록의 너비보다 항상 엄격히 작아야 한다. 따라서 가장 넓은 블록을 탑의 맨 아래에 놓고, 위로 올라갈수록 더 좁은 블록을 놓는다. 또한 탑이 보기 좋으려면 각 블록의 높이는 바로 아래 블록의 높이 이상이어야 한다. Dirk가 만들 수 있는 탑의 최대 높이를 계산하도록 도와주자.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$19$| $1 \leq N \leq 10$, $H_i \le 10^5$, $W_i = N+1 - i$, 즉 너비는 순서대로 $N$, $N-1$, $\dots$, $1$이다.

$2$ |$35$| $1 \leq N \leq 500$, $H_i \le 10^5$, $W_i = N+1 - i$

$3$ |$20$| $1 \leq N \leq 500$, $H_i \le 10^5$

$4$ |$26$| 추가 제한 없음

첫째 줄에 Dirk가 가진 블록의 수를 나타내는 정수 $N$ ($1 \leq N \leq 10^5$)가 주어진다. 이후 각 블록에 대한 $N$개의 줄이 주어진다. 이 중 $i$번째 줄에는 두 정수 $W_i$와 $H_i$ ($1 \leq W_i, H_i \leq 10^9$)가 주어지며, 이는 $i$번째 블록의 너비와 높이이다.

Dirk가 만들 수 있는 탑의 최대 높이를 나타내는 정수 하나를 출력한다.