Money Confusion :
Difficulty Level : Easy
Submissions : 85
Asked In :
Marks :10
: 0 | : 0
In a laundry, it happens that people forget to take their money out of pockets and the money is washed with the clothes. The laundry man simply takes the wet notes and puts them sequentially to dry in sunlight. He does not mix them up, for example if he gets $$$3$$$ notes from one pocket he places them sequentially and them places the notes received from other clothes and so on. Shane knows the amount of money he forgot in his trousers. You need to tell him the minimum number of notes that must be there in his pockets so that they amount to the mentioned sum. Return $$$-1$$$ if his amount is not possible.
The first line contains $$$2$$$ integers $$$n(1 \leq n \leq 2 \times 10^5)$$$, the number of notes the laundry man has and $$$k(1 \leq k \leq 10^{18})$$$ - the amount Shane forgot in his pockets.
The next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(1 \leq a_i \leq 10^9)$$$ - the values of the notes arranged sequentially.
Output a single integer - the minimum number of notes that make up Shane's amount.
6 15 1 4 20 3 10 5
2
