시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 6 6 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+MTxcL3N1Yj5cdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwOFx1YjU0YywgXHViM2Q5XHVjODA0XHVjNzQ0IFx1YmE4NyZuYnNwO1x1YWMxYyBcdWFjMDBcdWM4MzhcdWFjMDBcdWJhNzQmbmJzcDtcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViODVjIDFcdWJkODBcdWQxMzAgS1x1YWU0Y1x1YzljMFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVjOWMwXHViZDg4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/JnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzVkOFx1YjgwOFx1YzYyNFx1YjE3OFx1Yjc3Y1x1YjI5NCBcdWJhODcgXHVjZDA4IFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMzAwXHViMmY1XHVkNTg4XHVhY2UwLCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWMyYjVcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZxdW90O1x1Yzc3NFx1YjdmMCBcdWFlMzBcdWJjZjhcdWM4MDFcdWM3NzggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1Yzc3NFx1YzgxYyBcdWMyN2RcdWM4ZTAhJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzVkOFx1YjgwOFx1YzYyNFx1YjE3OFx1Yjc3Y1x1Yjk3YyBcdWIzYzRcdWM2NDBcdWM5MDQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJkMDVcdWMyZGNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMjE4XHVjNzc4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4Jm5ic3A7XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKE4mbGU7MTAwLDAwMClcdWFjZmMgSyhLJmxlOzEsMDAwLDAwMClcdWFjMDAgXHVjNzg1XHViODI1XHViNDE4XHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWIzZDlcdWM4MDQmbmJzcDtcdWFjMDBcdWNlNThBPHN1Yj5pPFwvc3ViPihBPHN1Yj5pPFwvc3ViPiZsZTsxMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMTFjXHVjYzI4IFx1ZDU2MFx1YmEzOFx1YjJjOFx1YWVkOFx1YzExYyZuYnNwO1x1YWMwMFx1YzgzOFx1YWMwMFx1YzE1NFx1YzU3YyZuYnNwO1x1ZDU1OFx1YjI5NCBcdWIzZDlcdWM4MDQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWI5Y2NcdWM1N2QgTlx1YWMxY1x1Yjk3YyBcdWIyZTQgXHVhYzAwXHVjODM4XHVhYzAwXHVjMTU0XHViM2M0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzNjXHVjMmRjXHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzNjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSaWRkbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5FbGxlb25vcmEmcnNxdW87cyBncmFuZG1vdGhlciAmbmRhc2g7IFNlcmNoYSBsb3ZlcyB0byBjaGFsbGVuZ2UgaGVyIGdyYW5kY2hpbGRyZW4gd2l0aCBhbGwga2luZHMgb2YgbWF0aGVtYXRpY2FsIHJpZGRsZXMuIER1cmluZyB0aGUgbGFzdCBmYW1pbHkgcmV1bmlvbiBzaGUgZ2F2ZSB0aGVtIHRoZSBmb2xsb3dpbmcgb25lOjxcL3A+XHJcblxyXG48cD4mbGRxdW87SW4gdGhlIG5laWdoYm9yaW5nIHN0b3JlIHRoZXJlIGFyZSBLIGdvb2RzIHdpdGggZGlmZmVyZW50IHByaWNlcyBmcm9tIDEgdG8gSy4gSSBoYXZlIE4gY29pbnMgaW4gdGhlIGZvbGxvd2luZyBvcmRlcjogQTEsIEEyLCAmaGVsbGlwOywgQW4uIEkgd2FudCB0byBnbyB0byB0aGUgc3RvcmUgYW5kIGJlIGFibGUgdG8gcGF5IHRoZSBleGFjdCBwcmljZSBmb3IgZWFjaCBnb29kLiBJbiB0aGUgc2FtZSB0aW1lIEkmcnNxdW87bSBhbiBvbGQgd29tYW4gYW5kIGRvbiZyc3F1bzt0IGxpa2UgY2FycnlpbmcgYWxsIGNvaW5zIHdpdGggbWUsIHNvIEkgd291bGQgbGlrZSB0byB0YWtlIG9ubHkgdGhlIGZpcnN0IGZldy4gSG93IG1hbnkgY29pbnMgc2hvdWxkIEkgdGFrZSB0byBiZSBhYmxlIHRvIHBheSBlYWNoIHByaWNlIGZyb20gMSB0byBLPyZyZHF1bzs8XC9wPlxyXG5cclxuPHA+RWxseSBkaWRuJnJzcXVvO3Qgc3BlbmQgbW9yZSB0aGFuIGEgZmV3IHNlY29uZHMgYmVmb3JlIGFuc3dlcmluZyBhbmQgdGhpbmtpbmcgJmxkcXVvO0FoLCBCYWJhIFNlcmNoYSwgbm90IHRoZXNlIHN0YW5kYXJkIGFsZ29yaXRobXMgYWdhaW4hJnJkcXVvOzxcL3A+XHJcblxyXG48cD5DYW4geW91IGNvbXBldGUgd2l0aCBFbGxlb25vcmEgYnkgd3JpdGluZyBhIHByb2dyYW0gdGhhdCBzb2x2ZXMgdGhlIGdpdmVuIHRhc2s/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgd2lsbCBiZSBnaXZlbiBvbmUgaW50ZWdlciBUICZuZGFzaDsgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzICZuZGFzaDsgb24gdGhlIGZpcnN0IHdpbGwgYmUgZ2l2ZW4gdGhlIGludGVnZXJzIE4gJmxlOyAxMDAsMDAwIGFuZCBLICZsZTsgMSwwMDAsMDAwLCBhbmQgb24gdGhlIHNlY29uZCAmbmRhc2g7IE4gaW50ZWdlcnMgXHUwNDEwaSAmbGU7IDEwMCwwMDAsIHJlcHJlc2VudGluZyB0aGUgY29pbiB2YWx1ZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IG9uIHRoZSBzdGFuZGFyZCBvdXRwdXQgb25lIHNvbGUgaW50ZWdlciAmbmRhc2g7IHRoZSBmaXJzdCBob3cgbWFueSBjb2lucyBzaG91bGQgRWxseSZyc3F1bztzIGdyYW5kbW90aGVyIHRha2UgaW4gb3JkZXIgdG8gYmUgYWJsZSB0byBwYXkgZWFjaCBzdW0gZnJvbSAxIHRvIEsuIElmIHRoaXMgaXMgbm90IHBvc3NpYmxlIGV2ZW4gYnkgdGFraW5nIGFsbCBOIG9mIHRoZW0sIHByaW50IC0xIGluc3RlYWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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