시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB375518.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+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHVjZDA4XHVhZTMwXHVjMThkXHViODI1IFYwICgwICZsdDsgVjAgJmxlOyAxMDAwKSBcdWM2NDAgXHViYzQwXHVjNzU4IFx1YzIxOCBuICgwICZsdDsgbiAmbGU7IDIwLDAwMCkgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1YmM0MFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHViNGU0XHVjNzQwJm5ic3A7XHViYzQwXHVjNzU4IHhcdWM4OGNcdWQ0NWMgKDAgJmx0OyB4ICZsZTsgMTAsMDAwKSBcdWM2NDAgXHViYzQwXHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM4MTBcdWM3NTggeVx1Yzg4Y1x1ZDQ1YyAoMCAmbHQ7IHkxICZsZTsgeTIgJmxlOyAxMCwwMDApIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzgxMFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVkNTVjXHVjOTA0XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3NDg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGFtc3RlciAyIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNvbXBldGl0aW9uIG9mIGZseWluZyBoYW1zdGVycyBpbiBIYW1zdGVyYnVyZy4gRWFjaCBjb21wZXRpbmcgaGFtc3RlciBpcyB0aHJvd24gZnJvbSBhIHNsaW5nLiBUaGUgaW5pdGlhbCBzcGVlZCBvZiB0aGUgaGFtc3RlcnMgaXMgVjxzdWI+MDxcL3N1Yj4gbVwvcy4gRnJlZSBmYWxsIGFjY2VsZXJhdGlvbiBpcyBnID0gMTAgbVwvczxzdXA+MjxcL3N1cD4uIFRoZXJlIGlzIG5vIGFpciBmcmljdGlvbi4gVGhlIHNpemUgb2YgdGhlIGhhbXN0ZXIgYW5kIHRoZSBzbGluZyBhcmUgbmVnbGlnaWJsZS4gV2hlbiB0aGUgaGFtc3RlciBpcyB0aHJvd24gZnJvbSB0aGUgc2xpbmcgaXRzIGFsdGl0dWRlIGlzIDAgbWV0ZXJzLiBUaGVyZSBpcyBhIG51bWJlciBvZiB2ZXJ0aWNhbCBnYXRlcyBpbiB0aGUgYWlyLiBFYWNoIGdhdGUgaGFzIGEgbG93ZXIgYW5kIGFuIHVwcGVyIGJvdW5kLiBJZiB3ZSBtYXJrIHRoZSBwb2ludHMgZGlyZWN0bHkgdW5kZXIgZWFjaCBvZiB0aGUgZ2F0ZXMgb24gdGhlIGdyb3VuZCAmbmRhc2g7IHRob3NlIHBvaW50cyBhcmUgcG9zaXRpb25lZCBpbiBvbmUgbGluZSBhbmQgb24gb25lIHNpZGUgZnJvbSB0aGUgc3RhcnRpbmcgcG9pbnQuIEEgaGFtc3RlciBnZXRzIGFzIG1hbnkgcG9pbnRzIGFzIHRoZSBhbW91bnQgb2YgZ2F0ZXMgaGUgZmxpZXMgdGhyb3VnaC4gWW91IGhhdmUgdG8gY2FsY3VsYXRlIHRoZSBtYXhpbWFsIGFtb3VudCBvZiBwb2ludHMgdGhhdCBhIGhhbXN0ZXIgY2FuIGdldCBpbiBvbmUgZmxpZ2h0LiBJdCBpcyBjb25zaWRlcmVkIHRoYXQgYSBoYW1zdGVyIGZsaWVzIHRocm91Z2ggdGhlIGdhdGUgaWYgaGUgdG91Y2hlcyB0aGUgYm91bmRzIG9mIHRoZSBnYXRlIGR1cmluZyB0aGUgZmxpZ2h0IG9mIGZsaWVzIGJldHdlZW4gdGhlIGJvdW5kcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBudW1iZXIgMCAmbHQ7IHQgJmx0Oz0gMTAgdGhlIGFtb3VudCBvZiB0ZXN0IGNhc2VzLiBUaGUgZGVzY3JpcHRpb24gb2YgZWFjaCB0ZXN0IGNhc2UgZm9sbG93cy4gRWFjaCB0ZXN0IHN0YXJ0cyB3aXRoIHR3byBpbnRlZ2VycyAwICZsdDsgVjxzdWI+MDxcL3N1Yj4gJmx0Oz0gMTAwMCAmbmRhc2g7IHRoZSBpbml0aWFsIHNwZWVkIG9mIHRoZSBoYW1zdGVyIGFuZCAwICZsdDsgbiAmbHQ7PSAyMDAwMCAmbmRhc2g7IHRoZSB0b3RhbCBhbW91bnQgb2YgZ2F0ZXMuIEVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBjb250YWlucyB0aGUgZGVzY3JpcHRpb24gb2Ygb25lIG9mIHRoZSBnYXRlczogdGhyZWUgaW50ZWdlcnMgMCAmbHQ7IHggJmx0Oz0gMTAwMDAgJm5kYXNoOyB0aGUgZGlzdGFuY2UgZnJvbSB0aGUgc3RhcnRpbmcgcG9pbnQgdG8gdGhlIHBvaW50IGRpcmVjdGx5IHVuZGVyIHRoZSBnYXRlLCAwICZsdDsgeTxzdWI+MTxcL3N1Yj4gJmx0Oz0geTxzdWI+MjxcL3N1Yj4gJmx0Oz0gMTAwMDAgJm5kYXNoOyBsb3dlciBhbmQgdXBwZXIgYm91bmQgb2YgdGhlIGdhdGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCB0aGUgbWF4aW1hbCBhbW91bnQgb2YgZ2F0ZXMgYSBoYW1zdGVyIGNhbiBmbHkgdGhyb3VnaCBpbiBvbmUgZmxpZ2h0IG9uIGEgc2VwYXJhdGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d