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

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 w_{i} metres wide and h_{i} metres
high, however he can rotate it so that it becomes h_{i} metres wide and w_{i}
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.

- 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 w
_{i}and h_{i}, representing the width and height of the ith box.

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

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 ≤ w_{i}, h_{i} ≤ 10,000.

- For Subtask 1 (20 points), all boxes will have identical dimensions. That
is, w
_{i}will be the same for all i and h_{i}will be the same for all i. - For Subtask 2 (40 points), all boxes will be squares. That is, w
_{i}= h_{i}for all i. - For Subtask 3 (40 points), no additional constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:49am AEDT