HAMSTER2 - Hamster Flight 2

no tags 

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 or flies between the bounds.

Input

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.

Output

For each test case output the maximal amount of gates a hamster can fly through in one flight on a separate line.

Example

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

hide comments
AAKASH TYAGI: 2014-01-12 10:26:08

can any one provide some more test cases???

:D: 2010-11-27 16:32:04

First think of a problem, when you want a hamster to pass a single gate. Then try to merge solutions for all the gates.

zetro: 2010-11-27 02:50:08

@spooky: so we must check in every gates that the hamster will pass....
is it right???
thanks be4...

Spooky: 2010-11-26 19:37:57

well... that's actually the best angle you should find... that is such angle that the hamster gets the most points...

zetro: 2010-11-26 16:24:51

@ spoky :do we need any kind of sorting here???
how about the angle???
please give me more hint.....i really confused..........

Last edit: 2010-11-26 16:33:41
Spooky: 2010-07-09 05:02:04

no bounce... he can't continue...

Ammar Qadri: 2010-07-03 20:12:21

Wait, just to be clear... if the hamster hits the grounds, he can no longer continue or is there bounce?

Mayank Singh: 2010-06-10 17:46:31

got it, angle that maximises number of gates has to be used...

Mayank Singh: 2010-06-10 17:46:31

why isn't angle of throw given? what angle do we take?


Added by:Spooky
Date:2010-04-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Open All-Ukrainian Collegiate Contest Semi-Final, 2010