Tower Building

Interview

Time limit3sMemory limit1024 MB

Summary

Given N blocks each with a square width and height, stack a subset so width strictly decreases upward while height weakly increases upward, maximizing the total tower height.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Binary search, Array
Solved: No attempts yet

Problem

Lille Dirk Ref wants to build as tall a tower as possible with his $N$ blocks. All blocks are rectangular cuboids with a square base, and a tower is a set of blocks stacked directly on top of one another (two blocks may not lie side by side). To keep the tower from becoming unstable and collapsing, the width of each block (that is, the side of the square base it stands on) must always be strictly less than the width of the block it stands on. So the tower is built with the widest blocks at the bottom and narrower blocks higher up. In addition, each block must be at least as tall as the block below it, so that the tower looks nice. Help Dirk compute the maximum height of a tower he can build.

Input

The first line contains an integer $N$ , the number of blocks Dirk has. Then follow $N$ lines, one for each block. On the $i$ th of these lines are two integers, the width $W_i$ of the $i$ th block, $1 \le W_i \le 10^9$ , and its height $H_i$ , $1 \le H_i \le 10^9$ .

Output

Print one line with an integer: the maximum height Dirk can build.

Constraints

$1 \le N \le 10^5$

Examples3

Example 1
Input
```
5
5 1
4 2
3 5
2 3
1 4
```
Expected output
```
10
```

Example 2

Input

Expected output

Example 3
Input
```
3
1 2
1 2
1 3
```
Expected output
```
3
```