시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 63 54 48 90.566%

문제

당신은 사탕 공장의 주인이다. 날마다, 당신은 J개의 사탕을 가게에 보내기 위해 상자에 포장해야 한다.

당신은 크기가 다른 상자 N개를 가지고 있다. 당신은 편리를 위해 상자를 최소한으로 쓰려고 한다. (박스를 다 채울 필요는 없다. 일부분만 채워도 된다.)

당신이 공장에서 나오는 사탕의 개수와 각 상자의 크기를 입력받고, 상자를 최소한으로 쓸 때의 사용되는 상자 개수를 출력하는 프로그램을 작성하라. 포장하기 전 사탕이 있는 곳은 충분히 넓다는 것을 보장한다.

입력

첫번째 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각각의 테스트 케이스는 아래 형식을 따른다.

테스트 케이스의 첫번째 줄에는 사탕의 개수 J와 상자의 개수 N이 주어진다. (1 ≤ J, N ≤ 1,000)

다음 N개의 줄에는 각각 줄마다 i번째 상자의 세로 길이 Ri 그리고 가로 길이 Ci가 주어진다. 상자의 크기는 다른 상자의 크기와 똑같을 수도 있다. 상자에는 Ri * Ci보다 더 많은 사탕을 포장할 수 없다. (1 ≤ Ri, Ci ≤ 10,000)

출력

출력은 T개의 줄로 이루어진다. 각각의 줄마다 i번째 테스트 케이스에서 최소한의 상자 개수를 출력하여야 한다.

예제 입력 1

1
20 5
3 4
2 5
1 8
3 3
2 5

예제 출력 1

2

예제 입력 2

2
12 3
2 7
1 5
3 2
20 3
2 7
1 5
3 2

예제 출력 2

1
2
W3sicHJvYmxlbV9pZCI6IjExMjU2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFjXHVkMGQ1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjMGFjXHVkMGQ1IFx1YWNmNVx1YzdhNVx1Yzc1OCBcdWM4ZmNcdWM3NzhcdWM3NzRcdWIyZTQuIFx1YjBhMFx1YjljOFx1YjJlNCwgXHViMmY5XHVjMmUwXHVjNzQwIEpcdWFjMWNcdWM3NTggXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YWMwMFx1YWM4Y1x1YzVkMCBcdWJjZjRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWQzZWNcdWM3YTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjJlNFx1Yjk3OCBcdWMwYzFcdWM3OTAgTlx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVkM2I4XHViOWFjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzNjXHViODVjIFx1YzRmMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIChcdWJjMTVcdWMyYTRcdWI5N2MgXHViMmU0IFx1Y2M0NFx1YzZiOCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM3N2NcdWJkODBcdWJkODRcdWI5Y2MgXHVjYzQ0XHVjNmNjXHViM2M0IFx1YjQxY1x1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc3NCBcdWFjZjVcdWM3YTVcdWM1ZDBcdWMxMWMgXHViMDk4XHVjNjI0XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVhYzAxIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHVhY2UwLCBcdWMwYzFcdWM3OTBcdWI5N2MgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzNjXHViODVjIFx1YzRmOCBcdWI1NGNcdWM3NTggXHVjMGFjXHVjNmE5XHViNDE4XHViMjk0IFx1YzBjMVx1Yzc5MCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YWUzMCBcdWM4MDQgXHVjMGFjXHVkMGQ1XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgXHVjZGE5XHViZDg0XHVkNzg4IFx1YjExM1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHVjN2E1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7Jm5ic3A7MTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjNTQ0XHViNzk4IFx1ZDYxNVx1YzJkZFx1Yzc0NCBcdWI1MzBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4IEpcdWM2NDAgXHVjMGMxXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IEosIE4gJmxlOyAxLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgaVx1YmM4OFx1YzlmOCBcdWMwYzFcdWM3OTBcdWM3NTggXHVjMTM4XHViODVjIFx1YWUzOFx1Yzc3NCBSPHN1Yj5pPFwvc3ViPiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzAwXHViODVjIFx1YWUzOFx1Yzc3NCBDPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViMmU0XHViOTc4IFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM2NDAgXHViNjExXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1Yzc5MFx1YzVkMFx1YjI5NCBSPHN1Yj5pPFwvc3ViPiAqIEM8c3ViPmk8XC9zdWI+XHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1ZDNlY1x1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiZuYnNwOygxICZsZTsgUjxzdWI+aTxcL3N1Yj4sIEM8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAxMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzkwNFx1YjljOFx1YjJlNCBpXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzBjMVx1Yzc5MCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTI1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkplbGx5IEJlYW4iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgYW4gb3duZXIgb2YgYSBjYW5keSBmYWN0b3J5LiBJbiBlYWNoIGRheSwgeW91IGhhdmUgdG8gcGFjayBKIGplbGx5IGJlYW5zIGludG8gYm94ZXMgZm9yIHRyYW5zZmVyIHRvIHRoZSBzdG9yZXMuPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIHNvbWUgYm94ZXMgd2hpY2ggbWF5IGJlIGRpZmZlcmVudCBpbiBkaW1lbnNpb24uIEZvciB5b3VyIGNvbnZlbmllbmNlLCB5b3Ugd2FudCB0byB1c2UgbGVhc3QgYm94ZXMgYXMgcG9zc2libGUuIChZb3UgZG8gbm90IG5lZWQgdG8gZmlsbCB1cCB0aGUgYm94LCBwYXJ0bHkgZmlsbCBpcyBhY2NlcHRhYmxlLik8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZ2V0IGEgbnVtYmVyIG9mIGplbGx5IGJlYW5zIHlvdSByZWNlaXZlIGZyb20gdGhlIGZhY3RvcnkgYW5kIGRpbWVuc2lvbiBvZiBlYWNoIGJveCBhbmQgZmluZCB0aGUgbnVtYmVyIG9mIGxlYXN0IGJveGVzIGNhbiBiZSB1c2VkLiBXZSBndWFyYW50ZWUgdGhhdCB0aGVyZSB3aWxsIGJlIHN1ZmZpY2llbnQgc3BhY2VzIGZvciB0aGUgamVsbHkgYmVhbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIGhhcyBhIG51bWJlciBUICgxICZsZTsgVCAmbGU7IDEwKSByZXByZXNlbnQgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGhhcyBhIGZvcm1hdCBhcyBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPkZpcnN0IGxpbmUgaGFzIHR3byBudW1iZXJzLCBKIGFuZCBOICgxICZsZTsgSiwgTiAmbGU7IDEsMDAwKSByZXByZXNlbnQgbnVtYmVyIG9mIGplbGx5IGJlYW5zIHlvdSByZWNlaXZlIGZyb20gdGhlIGZhY3RvcnkgYW5kIG51bWJlciBvZiBib3hlcyB5b3UgaGF2ZS48XC9wPlxyXG5cclxuPHA+Rm9yIG5leHQgTiBsaW5lcywgZWFjaCBsaW5lIGhhcyB0d28gbnVtYmVycyBSPHN1Yj5pPFwvc3ViPiBhbmQgQzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBSPHN1Yj5pPFwvc3ViPiwgQzxzdWI+aTxcL3N1Yj4gJmxlOyAxMCwwMDApIHJlcHJlc2VudCBkaW1lbnNpb24gKG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zKSBvZiBpLXRoIGJveCAoVGhlcmUgY2FuIGJlIHR3byBib3hlcyB3aXRoIHRoZSBzYW1lIGRpbWVuc2lvbi4pIFRoaXMgYm94IGNhbiBiZSBwYWNrZWQgd2l0aCBubyBtb3JlIHRoYW4gUjxzdWI+aTxcL3N1Yj4gKiBDPHN1Yj5pPFwvc3ViPiBqZWxseSBiZWFucy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIG91dHB1dCBzaG91bGQgaGF2ZSBUIGxpbmVzLiBFYWNoIGxpbmUgcmVwcmVzZW50IHRoZSBudW1iZXIgb2YgbGVhc3QgYm94ZXMgY2FuIGJlIHVzZWQgaW4gaS10aCB0ZXN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d