Rocket Stages

Many rockets are built from several stages to improve efficiency. When the fuel in one stage is used up, that stage can be dropped, reducing the weight the remaining rocket must carry. The first stage needs a powerful engine able to lift the whole rocket, while later stages can use smaller engines.

In this problem you must decide which stages to combine so that the rocket's upward velocity, once all fuel has burned, is as large as possible.

Each stage is described by four values:

• its empty mass $S$ (kilograms), without fuel;
• the mass $L$ (kilograms) of the fuel it carries;
• the thrust $T$ (newtons) produced by its engine;
• its fuel consumption $C$ (kilograms per second).

Assume the rocket points straight up throughout the flight. Two forces act on it: the engine's thrust of $T$ newtons upward, and gravity of $9.8M$ newtons downward, where $M$ is the rocket's current total mass in kilograms (including fuel). The rocket's acceleration is $F/M$ metres per second squared upward, where $F$ is the net force in newtons and $M$ is the current total mass. As soon as a stage burns out, it is discarded immediately and the next stage begins to burn. The rocket's final velocity is the integral of its net acceleration over time.

For safety, the net acceleration may never point downward until the rocket has run out of fuel. Also for safety, the rocket's total mass may not exceed $10000$ kilograms. The rocket must have at least one stage.

The first line contains one integer: the number of test cases.

Each test case begins with a line containing an integer $N$, the number of available stages ($N \le 1000$). The next $N$ lines each describe one stage with four integers $S$, $L$, $T$, and $C$, as defined above; each integer fits in a 32-bit unsigned value. You must keep the stages in the given order, but you may leave some of them out (possibly including the first). The stage listed first sits at the top of the rocket and therefore burns last. For every test case it is guaranteed that at least one rocket satisfying all the requirements can be built.

For each test case, output a single line with one integer: the maximum speed in metres per second that the rocket can reach once it has finished burning, rounded to the nearest metre per second.