Rocket Stages

Many rockets are made up of several stages to increase efficiency. When the fuel in one stage burns up, the stage can be discarded, reducing the weight of the remaining rocket. The first stage needs a strong engine capable of lifting the whole rocket, while later stages can have smaller engines.

In this problem, you will determine which stages to put together to maximize the upward velocity of the rocket when all the fuel has burned.

For each stage, you will be given:

• the mass S of the stage, in kilograms, when it is empty (without fuel),


• the mass L of the fuel, in kilograms, in the stage,


• the thrust T, in newtons, provided by the engine in the stage, and


• the fuel consumption C, in kilograms per second, of the stage.

Assume that the rocket points straight upward for the duration of the flight. Two forces act on the rocket: the force of the engine, which is T newtons upwards, and the force of gravity, which is 9.8 M newtons downwards, where M is the total mass of the rocket in kilograms, including fuel. The acceleration of the rocket is F divided by M metres per second per second upwards, where F is the total net force acting on the rocket in newtons, and M is the total mass of the rocket in kilograms, including fuel. As soon as a stage finishes burning, it is immediately discarded and the next stage starts to burn. The final velocity of the rocket is the integral of the net acceleration (due to gravity and the engine) over time.

Due to safety regulations, the net acceleration of the rocket is never allowed to be downwards, until the rocket runs out of fuel.

Also due to safety regulations, the total mass of the rocket cannot exceed 10000 kilograms.

The rocket must have at least one stage.

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer N, the number of rocket stages in the current test case. There will be no more than 1000 stages. This line is followed by N lines, one for each stage. Each of these lines contains the four integers S, L, T, C that describe a stage, as explained above. Each of these integers can be represented by a 32-bit unsigned binary number. The order of the stages as listed must be preserved but some stages (including, possibly, the first stage) may be left out of the rocket. The stage listed first is at the top of the rocket (and will burn last). For every test case in the input, it is always possible to construct at least one rocket satisfying all the requirements of the problem statement.

For each test case, output a line containing a single integer, the maximum possible speed in metres per second of the rocket when it has finished burning, rounded to the nearest metre per second.

1
1
9999 1 1000000 1

90

University of Waterloo Local Contest 2008.09