The skatepark's new ramps

The local skating park has been given a nancial incentive by the city to make the park interesting for skaters of all levels. The park wants to use the incentive to build a series of ramps, somewhat resembling a mountain range. When talking to some of the volunteers in the committee responsible for the project, you find out they're having diffculties deciding about the best con guration of the ramps. They know the number of ramps to be built, and for each ramp they agree on the range of the height for that ramp. They are still discussing exactly how high each ramp should be, since they can't a ord to have them all at their highest, but they do want to spend all of the budget. This is the most important issue in the debate: they can't agree whether they want the di erences between the ramps to be small, to give the full ride a more consistent feeling, or as big as possible, to create a more diverse set of challenges.

You also notice they don't really have a good idea what the possibilities are, leaving them stranded in 'what-if' discussions. You decide to help them out by showing them the options they have, both the ones where the di erence between the highest and lowest ramp is kept as small as possible, as well as the one where that di erence is as much as possible. Since the committee is mainly bickering over the allowable di erences, you decide to start out by just presenting them the minimum and maximum di erence-between the highest and lowest ramp. Luckily, the park has a lot of space, so you won't need to take the placement of the ramps into account. All ramps
have the same inclination, which is such that a ramp of height h will have a length 4h (measured at, not over the ramp).

The rst line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line with the integer number r (2 <=r<=10000), the number of ramps the park will place;
A line with the integer number m (0 <= m <=200000000 = 2*10^8), the number of cubic meters of concrete the park has money for;
r lines with two numbers, l and t (0.00 <=l <=t <= 100.00), separated by one space, the minimum and maximum height in meters of the r-th ramp.

You may assume all ramps are made entirely of concrete, and shaped as 1 meter wide prisms, with a triangle with two equal sides as base. A series of ramps within the given constraints and using all concrete is guaranteed to exist.

For each test case, the output contains one line with two numbers, separated by one space: the minimum difference between the highest and lowest ramp and the maximum difference between the highest and the lowest ramp. These numbers are rounded to two decimals.

1
3
36
1.00 4.00
1.00 4.00
1.00 4.00

0.00 3.00 

Figure 1: The example ramps with maximum difference.

BAPC 2008