There is a competition of flying hamsters in Hamsterburg.
Each competing hamster is thrown from a sling.
The initial speed of the hamsters is V0 m/s. Free fall acceleration is g = 10 m/s2 .
There is no air friction.
The size of the hamster and the sling are negligible.
When the hamster is thrown from the sling its altitude is 0 meters.
There is a number of vertical gates in the air.
Each gate has a lower and an upper bound.
If we mark the points directly under each of the gates on the ground,
those points are positioned in one line and on one side from the starting point.
A hamster gets as many points as the amount of gates he flies through.
You have to calculate the maximal amount of points that a hamster can get in one flight.
It is considered that a hamster flies through the gate if he touches the bounds of the gate during the flight of flies between the bounds.
The first line of the input contains number 0 < t <= 10 the amount of test cases. The description of each test case follows.
Each test starts with two integers 0 < V0 <= 1000 - the initial speed of the hamster and 0 < n <= 20000 - the total amount of gates. Each of the next n lines contains the description of one of the gates: three integers 0 < x <= 10000 - the distance from the starting point to the point directly under the gate, 0 < y1 <= y2 <= 10000 - lower and upper bound of the gate.
For each test case output the maximal amount of gates a hamster can fly through in one flight on a separate line.
3 10 2 3 1 2 3 2 3 10 3 1 1 1 2 2 3 3 4 6 10 3 1 1 2 2 3 4 3 5 6
2 1 2
Migrated from old NTUJ.
All-Ukrainian CPC 2010 Semi-Final
| No. | Testdata Range | Score |
|---|