Riddles
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?
Clarifications:
In the first test we can take all coins and construct all numbers up to 28, but our requirement is 10, so the first 4 are sufficient. In the second case we must be able to construct 1, 2 and 3, but we have to take all coins in order to have a one. The third case is impossible even with all coins.
“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?
InputOn 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.
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.
OutputFor 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.
Input
Output
3
7 10
1 2 3 4 5 6 7
3 3
2 4 1
3 6
3 1 4 Output
4
3
-1Clarifications:
In the first test we can take all coins and construct all numbers up to 28, but our requirement is 10, so the first 4 are sufficient. In the second case we must be able to construct 1, 2 and 3, but we have to take all coins in order to have a one. The third case is impossible even with all coins.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.