# Problem: Flatman's Tower

Want to try solving this problem? You can submit your code online if you log in or register.

## Flatman's Tower

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 128 MB

Flatman lives in the glorious country of Flatland. Apart from lacking a third dimension, Flatland is a beautiful place with bright flowers, rolling hills and burning sunsets which Flatman enjoys watching. Unfortunately Flatman does not see much of his land from the ground, so he would like to build a tall tower from which he can appreciate Flatland's natural beauty.

Flatman has N boxes. The ith box is wi metres wide and hi metres high, however he can rotate it so that it becomes hi metres wide and wi metres high. He would like to build the tallest tower of boxes subject to the following constraints:

• A box in the tower must be resting on either the ground or exactly one box below it.

• A box in the tower is either the highest box, or has exactly one box resting on top of it.

• A box must have width greater or equal to the box above it (after any rotations have been performed). That is, the tower can not have "overhang".

• The tower can not have a total height greater than H metres. If Flatman has his head above the clouds, he can't see very much of Flatland!

Flatman is having some difficulty solving this problem with his flat brain, so he has asked you, his third-dimensional friend, to assist him. Your task is to give Flatman the height of the tallest tower that can be constructed using his N boxes, without exceeding H metres.

### Input

• The first line of input will contain two space-separated integers N and H.

• The following N lines of input will each contain two space-separated integers wi and hi, representing the width and height of the ith box.

### Output

Output should consist of one line with one integer: the height of the tallest tower Flatman can construct. If it is not possible for Flatman to build a tower with height less than or equal to H metres, output 0.

```4 100
2 5
120 40
5 65
25 40
```

```95
```

### Explanation

In this example, Flatman has four boxes and can not exceed a height of 100m. It is possible to build a tower of height 95 by rotating the fourth box to be 40m wide and 25m tall and placing it on the ground, then placing the 5m x 65m box on top of it, finally placing the 2m x 5m box on top of that. The widths of the boxes are in non-decreasing order (40, 5, 2) and the heights have a sum of 95. It is not possible to build a higher tower that does not exceed 100m.

For all subtasks, 1 ≤ N ≤ 1,000 and 1 ≤ H ≤ 10,000. For each box i, 1 ≤ wi, hi ≤ 10,000.

• For Subtask 1 (20 points), all boxes will have identical dimensions. That is, wi will be the same for all i and hi will be the same for all i.

• For Subtask 2 (40 points), all boxes will be squares. That is, wi = hi for all i.

`Page generated: 22 May 2022,  6:14pm AEST`