시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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) 이다.

출력

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

예제 입력 1

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

예제 출력 1

2
1
2
W3sicHJvYmxlbV9pZCI6Ijc0ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NzVcdWFkZjhcdWI5YWMgXHViNzdjXHViYzE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjOGNcdWM3ODQgXHVhYzFjXHViYzFjXHVjNzkwXHVjNzc4IFx1Yzc0MFx1YWUzMFx1YjI5NCBBbmdyeSBCaXJkXHVjNjQwIEZsYXBweSBCaXJkIFx1Yjk3YyBcdWIyYTVcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWFjMWNcdWJjMWNcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWJjMTRcdWI4NWMmbmJzcDtBTFBTKEFuZ3J5IExhcnZhLCBQdW5pc2ggU25ha2VzKSBcdWM3NzRcdWIyZTQuIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWNlNzRcdWM2NDBcdWM3NzRcdWQ1NWMgXHViNzdjXHViYzE0XHViOTdjIFx1YjM1OFx1YzgzOFx1YzExYyBcdWJjNDBcdWI0ZTRcdWM3NDQgXHVjNGYwXHViN2VjXHVkMmI4XHViODI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzdjXHViYzE0XHVjNzU4IFx1YmMxY1x1YzBhY1x1YzljMFx1YzgxMFx1Yzc0MCAoMCwwKVx1Yzc3NFx1YWNlMCwgXHVjZDA4XHVhZTMwXHVjMThkXHViODI1KFx1YzE4ZFx1YjNjNFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQpXHVjNzQwIFYwIG1cL3NcdWI4NWMgXHVjODE1XHVkNTc0XHVjODM4XHVjNzg4XHVhY2UwLCBcdWM5MTFcdWI4MjVcdWFjMDBcdWMxOGRcdWIzYzQgZyA9IDEwbVwvc14yXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWI3N2NcdWJjMTRcdWI5N2MgXHVkMDZjXHVhZTMwXHVhYzAwIDBcdWM3NzggXHVjODEwXHVjNzNjXHViODVjLCZuYnNwO1x1ZDU0NFx1YjRkY1x1YzVkMCBcdWM3ODhcdWIyOTQmbmJzcDtcdWJjNDBcdWI0ZTRcdWM3NDQgeVx1Y2Q5NVx1YWNmYyBcdWQzYzlcdWQ1ODlcdWQ1NWMgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YmFhOFx1YjM3OFx1YjljMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NDRcdWM5YzEgXHVhYzFjXHViYzFjXHViMmU4XHVhY2M0XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjZjVcdWFlMzBcdWI5YzhcdWNjMzBcdWFjZmMgXHViYzQwXHVhY2ZjIFx1Y2RhOVx1YjNjY1x1ZDU4OFx1Yzc0NCBcdWI1NGNcdWM3NTggXHVjMThkXHViM2M0XHViY2MwXHVkNjU0XHViMjk0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjNDBcdWM3NDQgXHViOWRlXHVjZGM0XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWMxMjBcdWJkODQgXHVjMGFjXHVjNzc0XHViODVjIFx1Yjc3Y1x1YmMxNFx1YWMwMCBcdWM5YzBcdWIwOThcdWFjMTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwIDFcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjXHViNDFjXHViMmU0LiBcdWM3NDBcdWFlMzBcdWIyOTQgXHVjNzc0IEFMUFMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzljMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI0NTQgXHVjMGMxXHVkMGRjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIyZTRcdWFjMDAgXHVhYzAxIFx1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzljMFx1YzVkMFx1YzExYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzc0IFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4mbmJzcDtcdWQ2MDRcdWM3YWMgXHVjMmE0XHVkMTRjXHVjNzc0XHVjOWMwXHVjNzU4IFx1Y2QwOFx1YWUzMFx1YzE4ZFx1YjgyNSZuYnNwO1YwXHVjNjQwIFx1YmM0MFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzljMFx1YzVkMFx1YzExYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWFjZTBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzlmOCBcdWM5MDRcdWM1ZDQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0ICgwICZsdDsgdCAmbGU7IDEwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWQ2YzQgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYlx1YmM4OFx1YzdhYyBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtcdWNkMDhcdWFlMzBcdWMxOGRcdWI4MjUgVjAgKDAgJmx0OyBWMCAmbGU7IDEwMDApIFx1YzY0MCBcdWJjNDBcdWM3NTggXHVjMjE4IG4gKDAgJmx0OyBuICZsZTsgMjAsMDAwKSBcdWI0NTBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViYzQwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWI0ZTRcdWM3NDAmbmJzcDtcdWJjNDBcdWM3NTggeFx1Yzg4Y1x1ZDQ1YyAoMCAmbHQ7IHggJmxlOyAxMCwwMDApIFx1YzY0MCBcdWJjNDBcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc1OCB5XHVjODhjXHVkNDVjICgwICZsdDsgeTEgJmxlOyB5MiAmbGU7IDEwLDAwMCkgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODEwXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWQ1NWNcdWM5MDRcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc0ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIYW1zdGVyIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgY29tcGV0aXRpb24gb2YgZmx5aW5nIGhhbXN0ZXJzIGluIEhhbXN0ZXJidXJnLiBFYWNoIGNvbXBldGluZyBoYW1zdGVyIGlzIHRocm93biBmcm9tIGEgc2xpbmcuIFRoZSBpbml0aWFsIHNwZWVkIG9mIHRoZSBoYW1zdGVycyBpcyBWPHN1Yj4wPFwvc3ViPiBtXC9zLiBGcmVlIGZhbGwgYWNjZWxlcmF0aW9uIGlzIGcgPSAxMCBtXC9zPHN1cD4yPFwvc3VwPi4gVGhlcmUgaXMgbm8gYWlyIGZyaWN0aW9uLiBUaGUgc2l6ZSBvZiB0aGUgaGFtc3RlciBhbmQgdGhlIHNsaW5nIGFyZSBuZWdsaWdpYmxlLiBXaGVuIHRoZSBoYW1zdGVyIGlzIHRocm93biBmcm9tIHRoZSBzbGluZyBpdHMgYWx0aXR1ZGUgaXMgMCBtZXRlcnMuIFRoZXJlIGlzIGEgbnVtYmVyIG9mIHZlcnRpY2FsIGdhdGVzIGluIHRoZSBhaXIuIEVhY2ggZ2F0ZSBoYXMgYSBsb3dlciBhbmQgYW4gdXBwZXIgYm91bmQuIElmIHdlIG1hcmsgdGhlIHBvaW50cyBkaXJlY3RseSB1bmRlciBlYWNoIG9mIHRoZSBnYXRlcyBvbiB0aGUgZ3JvdW5kICZuZGFzaDsgdGhvc2UgcG9pbnRzIGFyZSBwb3NpdGlvbmVkIGluIG9uZSBsaW5lIGFuZCBvbiBvbmUgc2lkZSBmcm9tIHRoZSBzdGFydGluZyBwb2ludC4gQSBoYW1zdGVyIGdldHMgYXMgbWFueSBwb2ludHMgYXMgdGhlIGFtb3VudCBvZiBnYXRlcyBoZSBmbGllcyB0aHJvdWdoLiBZb3UgaGF2ZSB0byBjYWxjdWxhdGUgdGhlIG1heGltYWwgYW1vdW50IG9mIHBvaW50cyB0aGF0IGEgaGFtc3RlciBjYW4gZ2V0IGluIG9uZSBmbGlnaHQuIEl0IGlzIGNvbnNpZGVyZWQgdGhhdCBhIGhhbXN0ZXIgZmxpZXMgdGhyb3VnaCB0aGUgZ2F0ZSBpZiBoZSB0b3VjaGVzIHRoZSBib3VuZHMgb2YgdGhlIGdhdGUgZHVyaW5nIHRoZSBmbGlnaHQgb2YgZmxpZXMgYmV0d2VlbiB0aGUgYm91bmRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIG51bWJlciAwICZsdDsgdCAmbHQ7PSAxMCB0aGUgYW1vdW50IG9mIHRlc3QgY2FzZXMuIFRoZSBkZXNjcmlwdGlvbiBvZiBlYWNoIHRlc3QgY2FzZSBmb2xsb3dzLiBFYWNoIHRlc3Qgc3RhcnRzIHdpdGggdHdvIGludGVnZXJzIDAgJmx0OyBWPHN1Yj4wPFwvc3ViPiAmbHQ7PSAxMDAwICZuZGFzaDsgdGhlIGluaXRpYWwgc3BlZWQgb2YgdGhlIGhhbXN0ZXIgYW5kIDAgJmx0OyBuICZsdDs9IDIwMDAwICZuZGFzaDsgdGhlIHRvdGFsIGFtb3VudCBvZiBnYXRlcy4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW5zIHRoZSBkZXNjcmlwdGlvbiBvZiBvbmUgb2YgdGhlIGdhdGVzOiB0aHJlZSBpbnRlZ2VycyAwICZsdDsgeCAmbHQ7PSAxMDAwMCAmbmRhc2g7IHRoZSBkaXN0YW5jZSBmcm9tIHRoZSBzdGFydGluZyBwb2ludCB0byB0aGUgcG9pbnQgZGlyZWN0bHkgdW5kZXIgdGhlIGdhdGUsIDAgJmx0OyB5PHN1Yj4xPFwvc3ViPiAmbHQ7PSB5PHN1Yj4yPFwvc3ViPiAmbHQ7PSAxMDAwMCAmbmRhc2g7IGxvd2VyIGFuZCB1cHBlciBib3VuZCBvZiB0aGUgZ2F0ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IHRoZSBtYXhpbWFsIGFtb3VudCBvZiBnYXRlcyBhIGhhbXN0ZXIgY2FuIGZseSB0aHJvdWdoIGluIG9uZSBmbGlnaHQgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==