G. Crappy Typing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of the most anticipated events of the Office Olympics is speed typing. Employees compete by taking a typing test. There are $$$N$$$ employees participating, and since there are limited computers, employees must wait in line to take the test.

In preparation for the event, Manager Michael needs to set up $$$M$$$ computers, which can accommodate $$$M$$$ employees taking the test simultaneously. From last year's competition data, Michael estimates that the $$$i$$$-th employee will take $$$t_i$$$ time to finish the test. At the beginning of the contest, the first $$$M$$$ employees in line will start at an arbitrary computer. The moment an employee finishes the test, the next employee in line will take their place at the same computer. The contest ends when the $$$N$$$-th employee in line finishes the test.

To ensure that the next event can start on time, the entire typing contest must end within $$$D$$$ total time units or less. As Michael is lazy, please help him find the smallest possible value of $$$M$$$ that will ensure the contest finishes within $$$D$$$ total time units or less.

Input

The first line of input contains two integers $$$N, D$$$ ($$$1 \leq N \leq 10^5, 1 \leq D \leq 10^9$$$) as described above.

The next line of input contains $$$N$$$ integers separated by spaces. The $$$i^{th}$$$ integer denotes $$$t_i$$$ ($$$1 \leq t_i \leq 10^4$$$).

It is guaranteed that $$$M$$$ exists with the given input.

Output

Output a single line containing $$$M$$$, the minimum number of computers required.

Examples
Input
6 151
56 94 95 33 62 28
Output
3
Input
9 83
10 47 53 9 83 33 15 24 28
Output
5