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.
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
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.