시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 37 5 5 18.519%

문제

게임 개발자인 은기는 Angry Bird와 Flappy Bird 를 능가하는 새로운 게임을 개발하기로 했다. 바로 ALPS(Angry Larva, Punish Snakes) 이다. 우리는 카와이한 라바를 던져서 뱀들을 쓰러트려야 한다.

라바의 발사지점은 (0,0)이고, 초기속력(속도가 아니다)은 V0 m/s로 정해져있고, 중력가속도 g = 10m/s^2이다. 이 게임에서 우리는 라바를 크기가 0인 점으로, 필드에 있는 뱀들을 y축과 평행한 선분으로 모델링할 수 있다. 아직 개발단계이기 때문에 공기마찰과 뱀과 충돌했을 때의 속도변화는 고려하지 않는 상황이다.

뱀을 맞췄다는 것은 선분 사이로 라바가 지나갔다는 것이고, 이 경우 1점을 얻게된다. 은기는 이 ALPS 게임의 스테이지를 만들어둔 상태다. 그러다가 각 스테이지에서 얻을 수 있는 점수의 최대값이 궁금해졌다. 현재 스테이지의 초기속력 V0와 뱀들의 위치가 주어졌을 때, 이 스테이지에서 얻을 수 있는 최고점수를 구해보자.

입력

첫 째 줄엔 테스트케이스의 개수 t (0 < t ≤ 10) 가 주어진다. 이후 각 테스트케이스에 대해 아래와 같은 정보가 주어진다.

각 테스트케이스마다 첫번재 줄에는 초기속력 V0 (0 < V0 ≤ 1000) 와 뱀의 수 n (0 < n ≤ 20,000) 두개의 정수가 주어진다. 

그 다음 n개의 줄에 걸쳐서 뱀의 정보가 세 개의 정수로 주어진다. 이 수들은 뱀의 x좌표 (0 < x ≤ 10,000) 와 뱀의 양 끝점의 y좌표 (0 < y1 ≤ y2 ≤ 10,000) 이다.

출력

각 테스트케이스마다 얻을 수 있는 점수의 최대값을 한줄씩 출력한다.

예제 입력

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

힌트