시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 71 61 54 90.000%

문제

당신은 사탕 공장의 주인이다. 날마다, 당신은 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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoMSAmbGU7IFQgJmxlOyZuYnNwOzEwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzU0NFx1Yjc5OCBcdWQ2MTVcdWMyZGRcdWM3NDQgXHViNTMwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMTggSlx1YzY0MCBcdWMwYzFcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgSiwgTiAmbGU7IDEsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBpXHViYzg4XHVjOWY4IFx1YzBjMVx1Yzc5MFx1Yzc1OCBcdWMxMzhcdWI4NWMgXHVhZTM4XHVjNzc0IFI8c3ViPmk8XC9zdWI+IFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IEM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGMxXHVjNzkwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWIyZTRcdWI5NzggXHVjMGMxXHVjNzkwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWI2MTFcdWFjMTlcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVjNzkwXHVjNWQwXHViMjk0IFI8c3ViPmk8XC9zdWI+ICogQzxzdWI+aTxcL3N1Yj5cdWJjZjRcdWIyZTQgXHViMzU0IFx1YjljZVx1Yzc0MCBcdWMwYWNcdWQwZDVcdWM3NDQgXHVkM2VjXHVjN2E1XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuJm5ic3A7KDEgJmxlOyBSPHN1Yj5pPFwvc3ViPiwgQzxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOTA0XHViOWM4XHViMmU0IGlcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVjMGMxXHVjNzkwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMjU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSmVsbHkgQmVhbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBhbiBvd25lciBvZiBhIGNhbmR5IGZhY3RvcnkuIEluIGVhY2ggZGF5LCB5b3UgaGF2ZSB0byBwYWNrIEogamVsbHkgYmVhbnMgaW50byBib3hlcyBmb3IgdHJhbnNmZXIgdG8gdGhlIHN0b3Jlcy48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgc29tZSBib3hlcyB3aGljaCBtYXkgYmUgZGlmZmVyZW50IGluIGRpbWVuc2lvbi4gRm9yIHlvdXIgY29udmVuaWVuY2UsIHlvdSB3YW50IHRvIHVzZSBsZWFzdCBib3hlcyBhcyBwb3NzaWJsZS4gKFlvdSBkbyBub3QgbmVlZCB0byBmaWxsIHVwIHRoZSBib3gsIHBhcnRseSBmaWxsIGlzIGFjY2VwdGFibGUuKTxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBnZXQgYSBudW1iZXIgb2YgamVsbHkgYmVhbnMgeW91IHJlY2VpdmUgZnJvbSB0aGUgZmFjdG9yeSBhbmQgZGltZW5zaW9uIG9mIGVhY2ggYm94IGFuZCBmaW5kIHRoZSBudW1iZXIgb2YgbGVhc3QgYm94ZXMgY2FuIGJlIHVzZWQuIFdlIGd1YXJhbnRlZSB0aGF0IHRoZXJlIHdpbGwgYmUgc3VmZmljaWVudCBzcGFjZXMgZm9yIHRoZSBqZWxseSBiZWFucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgaGFzIGEgbnVtYmVyIFQgKDEgJmxlOyBUICZsZTsgMTApIHJlcHJlc2VudCBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaGFzIGEgZm9ybWF0IGFzIGZvbGxvdy48XC9wPlxyXG5cclxuPHA+Rmlyc3QgbGluZSBoYXMgdHdvIG51bWJlcnMsIEogYW5kIE4gKDEgJmxlOyBKLCBOICZsZTsgMSwwMDApIHJlcHJlc2VudCBudW1iZXIgb2YgamVsbHkgYmVhbnMgeW91IHJlY2VpdmUgZnJvbSB0aGUgZmFjdG9yeSBhbmQgbnVtYmVyIG9mIGJveGVzIHlvdSBoYXZlLjxcL3A+XHJcblxyXG48cD5Gb3IgbmV4dCBOIGxpbmVzLCBlYWNoIGxpbmUgaGFzIHR3byBudW1iZXJzIFI8c3ViPmk8XC9zdWI+IGFuZCBDPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IFI8c3ViPmk8XC9zdWI+LCBDPHN1Yj5pPFwvc3ViPiAmbGU7IDEwLDAwMCkgcmVwcmVzZW50IGRpbWVuc2lvbiAobnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMpIG9mIGktdGggYm94IChUaGVyZSBjYW4gYmUgdHdvIGJveGVzIHdpdGggdGhlIHNhbWUgZGltZW5zaW9uLikgVGhpcyBib3ggY2FuIGJlIHBhY2tlZCB3aXRoIG5vIG1vcmUgdGhhbiBSPHN1Yj5pPFwvc3ViPiAqIEM8c3ViPmk8XC9zdWI+IGplbGx5IGJlYW5zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgb3V0cHV0IHNob3VsZCBoYXZlIFQgbGluZXMuIEVhY2ggbGluZSByZXByZXNlbnQgdGhlIG51bWJlciBvZiBsZWFzdCBib3hlcyBjYW4gYmUgdXNlZCBpbiBpLXRoIHRlc3QgY2FzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=