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

문제

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

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

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

4
3
-1

힌트

출처

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