Stacking Boxes

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Java 2.0s
Python 1.5s
Memory limit: 256M

Problem type

You have N boxes with varying dimensions of w \times h (width by height).

You are trying to create the tallest tower possible by stacking any combination of these boxes. In order to keep your tower balanced, you can only stack a box on top of another if its width is strictly less than the one below it. Assuming you do not place any boxes next to each other, what is the height of the tallest possible tower you can create?


1 \le N, w \le 10^6

1 \le h \le 2\,000

Input Specification

The first line of input contains an integer N.

The next N lines of input each contain 2 space-separated integers, w and h.

Output Specification

Output the height of the tallest possible tower.

The height of any given tower is the sum of the heights of its boxes.

Sample Input

5 2
5 3
2 10

Sample Output


Explanation for Sample

You can use the 5 \times 3 box as the base of the tower and stack the 2 \times 10 box on top of it.


There are no comments at the moment.