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

문제

엘레오노라의 할머니 서차(Sercha)는 손녀, 손자들에게 수학 수수께끼를 내는 것을 좋아하십니다. 저번 가족여행에서는 이 문제를 내주셨습니다 :

"만약 어떤 가게에 K개의 상품을 팔고 있고 가격은 1에서 K라고 한다면, 내가 N개의 동전을 갖고 있고 그 동전은 A1,A2,. . .,AN이라고 한다. 나는 너무 늙어서 딱 그 가격에 최소 개수를 가져가고 싶어. 동전을 A1부터 차례대로 가져갈때, 동전을 몇 개 가져가면 최소 갯수로 1부터 K까지의 가격을 지불할 수 있을까?"

엘레오노라는 몇 초 지나지 않고 대답했고, 생각했습다.

"이런 기본적인 알고리즘은 이제 쉽죠!"

엘레오노라를 도와줄 프로그램을 작성해 봅시다.

입력

첫 줄에는 테스트 케이스 수인 T가 주어집니다. 각 케이스의 첫째 줄에는 N(N≤100,000)과 K(K≤1,000,000)가 입력되고 둘째 줄에는 N개의 정수 동전 가치Ai(Ai≤100,000)가 주어집니다.

출력

각 테스트 케이스마다 서차 할머니께서 가져가셔야 하는 동전 개수를 출력하고 만약 N개를 다 가져가셔도 할 수 없으시다면 -1을 출력한다.

예제 입력 1

3
7 10
1 2 3 4 5 6 7
3 3
2 4 1
3 6
3 1 4

예제 출력 1

4
3
-1
W3sicHJvYmxlbV9pZCI6IjMzNjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWMyMThcdWFlZDhcdWIwN2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzVkOFx1YjgwOFx1YzYyNFx1YjE3OFx1Yjc3Y1x1Yzc1OCBcdWQ1NjBcdWJhMzhcdWIyYzggXHVjMTFjXHVjYzI4KFNlcmNoYSlcdWIyOTQgXHVjMTkwXHViMTQwLCBcdWMxOTBcdWM3OTBcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMjE4XHVkNTU5Jm5ic3A7XHVjMjE4XHVjMjE4XHVhZWQ4XHViMDdjXHViOTdjIFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHVjMmVkXHViMmM4XHViMmU0LiBcdWM4MDBcdWJjODggXHVhYzAwXHVjODcxXHVjNWVjXHVkNTg5XHVjNWQwXHVjMTFjXHViMjk0IFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViMGI0XHVjOGZjXHVjMTY4XHVjMmI1XHViMmM4XHViMmU0IDo8XC9wPlxyXG5cclxuPHA+JnF1b3Q7XHViOWNjXHVjNTdkIFx1YzViNFx1YjVhNCBcdWFjMDBcdWFjOGNcdWM1ZDAgS1x1YWMxY1x1Yzc1OCBcdWMwYzFcdWQ0ODhcdWM3NDQgXHVkMzE0XHVhY2UwIFx1Yzc4OFx1YWNlMCBcdWFjMDBcdWFjYTlcdWM3NDAgMVx1YzVkMFx1YzExYyBLXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHViMGI0XHVhYzAwIE5cdWFjMWNcdWM3NTggXHViM2Q5XHVjODA0XHVjNzQ0IFx1YWMxNlx1YWNlMCBcdWM3ODhcdWFjZTAgXHVhZGY4IFx1YjNkOVx1YzgwNFx1Yzc0MCBBPHN1Yj4xPFwvc3ViPixBPHN1Yj4yPFwvc3ViPiw8c3Ryb25nPjxzdXA+LiAuJm5ic3A7LjxcL3N1cD48XC9zdHJvbmc+LEE8c3ViPk48XC9zdWI+XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViMDk4XHViMjk0IFx1YjEwOFx1YmIzNCBcdWIyOTlcdWM1YjRcdWMxMWMgXHViNTMxIFx1YWRmOCBcdWFjMDBcdWFjYTlcdWM1ZDAgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjZTAgXHVjMmY2XHVjNWI0LiBcdWIzZDlcdWM4MDRcdWM3NDQgQTxzdWI+MTxcL3N1Yj5cdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwOFx1YjU0YywgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YmE4NyZuYnNwO1x1YWMxYyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQmbmJzcDtcdWNkNWNcdWMxOGMgXHVhYzJmXHVjMjE4XHViODVjIDFcdWJkODBcdWQxMzAgS1x1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVjOWMwXHViZDg4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/JnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzVkOFx1YjgwOFx1YzYyNFx1YjE3OFx1Yjc3Y1x1YjI5NCBcdWJhODcgXHVjZDA4IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMzAwXHViMmY1XHVkNTg4XHVhY2UwLCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWMyYjVcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZxdW90O1x1Yzc3NFx1YjdmMCBcdWFlMzBcdWJjZjhcdWM4MDFcdWM3NzggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1Yzc3NFx1YzgxYyBcdWMyN2RcdWM4ZTAhJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzVkOFx1YjgwOFx1YzYyNFx1YjE3OFx1Yjc3Y1x1Yjk3YyBcdWIzYzRcdWM2NDBcdWM5MDQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJkMDVcdWMyZGNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMjE4XHVjNzc4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4Jm5ic3A7XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKE4mbGU7MTAwLDAwMClcdWFjZmMgSyhLJmxlOzEsMDAwLDAwMClcdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWIzZDlcdWM4MDQmbmJzcDtcdWFjMDBcdWNlNThBPHN1Yj5pPFwvc3ViPihBPHN1Yj5pPFwvc3ViPiZsZTsxMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMTFjXHVjYzI4IFx1ZDU2MFx1YmEzOFx1YjJjOFx1YWVkOFx1YzExYyZuYnNwO1x1YWMwMFx1YzgzOFx1YWMwMFx1YzE1NFx1YzU3YyZuYnNwO1x1ZDU1OFx1YjI5NCBcdWIzZDlcdWM4MDQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWI5Y2NcdWM1N2QgTlx1YWMxY1x1Yjk3YyBcdWIyZTQgXHVhYzAwXHVjODM4XHVhYzAwXHVjMTU0XHViM2M0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzNjXHVjMmRjXHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmlkZGxlcyIsImRlc2NyaXB0aW9uIjoiPHA+RWxsZW9ub3JhJnJzcXVvO3MgZ3JhbmRtb3RoZXIgJm5kYXNoOyBTZXJjaGEgbG92ZXMgdG8gY2hhbGxlbmdlIGhlciBncmFuZGNoaWxkcmVuIHdpdGggYWxsIGtpbmRzIG9mIG1hdGhlbWF0aWNhbCByaWRkbGVzLiBEdXJpbmcgdGhlIGxhc3QgZmFtaWx5IHJldW5pb24gc2hlIGdhdmUgdGhlbSB0aGUgZm9sbG93aW5nIG9uZTo8XC9wPlxyXG5cclxuPHA+JmxkcXVvO0luIHRoZSBuZWlnaGJvcmluZyBzdG9yZSB0aGVyZSBhcmUgSyBnb29kcyB3aXRoIGRpZmZlcmVudCBwcmljZXMgZnJvbSAxIHRvIEsuIEkgaGF2ZSBOIGNvaW5zIGluIHRoZSBmb2xsb3dpbmcgb3JkZXI6IEExLCBBMiwgJmhlbGxpcDssIEFuLiBJIHdhbnQgdG8gZ28gdG8gdGhlIHN0b3JlIGFuZCBiZSBhYmxlIHRvIHBheSB0aGUgZXhhY3QgcHJpY2UgZm9yIGVhY2ggZ29vZC4gSW4gdGhlIHNhbWUgdGltZSBJJnJzcXVvO20gYW4gb2xkIHdvbWFuIGFuZCBkb24mcnNxdW87dCBsaWtlIGNhcnJ5aW5nIGFsbCBjb2lucyB3aXRoIG1lLCBzbyBJIHdvdWxkIGxpa2UgdG8gdGFrZSBvbmx5IHRoZSBmaXJzdCBmZXcuIEhvdyBtYW55IGNvaW5zIHNob3VsZCBJIHRha2UgdG8gYmUgYWJsZSB0byBwYXkgZWFjaCBwcmljZSBmcm9tIDEgdG8gSz8mcmRxdW87PFwvcD5cclxuXHJcbjxwPkVsbHkgZGlkbiZyc3F1bzt0IHNwZW5kIG1vcmUgdGhhbiBhIGZldyBzZWNvbmRzIGJlZm9yZSBhbnN3ZXJpbmcgYW5kIHRoaW5raW5nICZsZHF1bztBaCwgQmFiYSBTZXJjaGEsIG5vdCB0aGVzZSBzdGFuZGFyZCBhbGdvcml0aG1zIGFnYWluISZyZHF1bzs8XC9wPlxyXG5cclxuPHA+Q2FuIHlvdSBjb21wZXRlIHdpdGggRWxsZW9ub3JhIGJ5IHdyaXRpbmcgYSBwcm9ncmFtIHRoYXQgc29sdmVzIHRoZSBnaXZlbiB0YXNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IHdpbGwgYmUgZ2l2ZW4gb25lIGludGVnZXIgVCAmbmRhc2g7IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lcyAmbmRhc2g7IG9uIHRoZSBmaXJzdCB3aWxsIGJlIGdpdmVuIHRoZSBpbnRlZ2VycyBOICZsZTsgMTAwLDAwMCBhbmQgSyAmbGU7IDEsMDAwLDAwMCwgYW5kIG9uIHRoZSBzZWNvbmQgJm5kYXNoOyBOIGludGVnZXJzIFx1MDQxMGkgJmxlOyAxMDAsMDAwLCByZXByZXNlbnRpbmcgdGhlIGNvaW4gdmFsdWVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCBvbiB0aGUgc3RhbmRhcmQgb3V0cHV0IG9uZSBzb2xlIGludGVnZXIgJm5kYXNoOyB0aGUgZmlyc3QgaG93IG1hbnkgY29pbnMgc2hvdWxkIEVsbHkmcnNxdW87cyBncmFuZG1vdGhlciB0YWtlIGluIG9yZGVyIHRvIGJlIGFibGUgdG8gcGF5IGVhY2ggc3VtIGZyb20gMSB0byBLLiBJZiB0aGlzIGlzIG5vdCBwb3NzaWJsZSBldmVuIGJ5IHRha2luZyBhbGwgTiBvZiB0aGVtLCBwcmludCAtMSBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Junior Balkan Olympiad in Informatics > JBOI 2009 2번