AIOC Banner

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:

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

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.

Sample Input

4 100
2 5
120 40
5 65
25 40

Sample Output

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.

Subtasks

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

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated:  1 December 2021, 11:49am AEDT