AlgoUniversity
  • Go Back
Discussion
Money Confusion :

Author

Ayush Kumar Shaw

Difficulty Level : Easy

Submissions : 89

Asked In : Nagarro

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.

Input

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

Output a single integer - the minimum number of notes that make up Shane's amount.

Example

Input
6 15
1 4 20 3 10 5
Output
2

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.