2830. Hamster 2

单点时限: 2.0 sec

内存限制: 256 MB

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.

样例

Input
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
Output
2
1
2

5 人解决,7 人已尝试。

10 份提交通过,共有 32 份提交。

7.3 EMB 奖励。

创建: 10 年,2 月前.

修改: 3 年,3 月前.

最后提交: 4 年,8 月前.

来源: Ukrainian

题目标签