D. Tasks at Odoo
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At Odoo, several tasks are processed daily on our dedicated servers. These tasks need to be inspected by a person who guarantees correct performance in all of them.

Natan is in charge this week, but he needs to finish all the tasks within the time limit set for him. However, to save more resources, Natan needs to find out the smallest amount of dedicated servers that will be needed to finish all tasks within the time limit or verify that this is impossible.

Each task takes a certain duration to perform. All the tasks need to be started in order (i.e., task $$$i$$$ just can start if task $$$i-1$$$ starts at the same time or at an earlier time).

Each dedicated server can only perform a maximum of one task at a time and it can start a new task as soon as it finishes the one it is currently doing.

As a new developer at Odoo, you were tasked with helping Natan solve this problem. Find out the smallest number of dedicated servers needed to perform these tasks or, if impossible, print the number -1.

Input

The first line contains two integers, $$$N$$$ and $$$T$$$ $$$(1 \leq N, T \leq 10^{5})$$$, representing the number of tasks and the time limit to do the tasks, respectively.

The second line contains $$$n$$$ integers $$$A_{i}$$$ $$$(1 \leq A_{i} \leq 10^{5})$$$, where $$$A_{i}$$$ represents the duration of the task $$$i$$$.

Output

Print a number $$$Q$$$ containing the smallest number of dedicated servers needed to perform these tasks or if it is impossible to do all the tasks within the time print the number -1.

Examples
Input
5 1
1 1 1 1 1
Output
5
Input
5 5
1 1 1 1 1
Output
1
Input
5 5
1 2 3 5 6
Output
-1