|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
Elleonora’s grandmother – Sercha loves to challenge her grandchildren with all kinds of mathematical riddles. During the last family reunion she gave them the following one:
“In the neighboring store there are K goods with different prices from 1 to K. I have N coins in the following order: A1, A2, …, An. I want to go to the store and be able to pay the exact price for each good. In the same time I’m an old woman and don’t like carrying all coins with me, so I would like to take only the first few. How many coins should I take to be able to pay each price from 1 to K?”
Elly didn’t spend more than a few seconds before answering and thinking “Ah, Baba Sercha, not these standard algorithms again!”
Can you compete with Elleonora by writing a program that solves the given task?
On the first line of the standard input will be given one integer T – the number of test cases. Each case consists of two lines – on the first will be given the integers N ≤ 100,000 and K ≤ 1,000,000, and on the second – N integers Аi ≤ 100,000, representing the coin values.
For each test case print on the standard output one sole integer – the first how many coins should Elly’s grandmother take in order to be able to pay each sum from 1 to K. If this is not possible even by taking all N of them, print -1 instead.
3 7 10 1 2 3 4 5 6 7 3 3 2 4 1 3 6 3 1 4
4 3 -1