Problem Description

$\text{Mislav}$ likes spending time in the forest the most, because there are all kinds of fruits in the forest, and eating each fruit gives a certain amount of fullness. However, he will not let his total fullness exceed $C$.

Now there is a path in the forest. Along the path, there are $N$ fruits planted in order, and each fruit has a fullness value $w_i$. $\text{Mislav}$ may choose to start from any fruit position and move forward toward the $N$-th fruit. While moving, if eating the fruit at the current position would not make the total fullness exceed $C$, then he will definitely eat that fruit. Otherwise, he will skip that fruit and continue moving.

What is the maximum number of fruits that $\text{Mislav}$ can eat?

Input Format

The first line contains two integers $N$ and $C$.

The second line contains $N$ integers $w_i$, the fullness value of the $i$-th fruit.

Output Format

Output one integer, the maximum number of fruits that $\text{Mislav}$ can eat.

5 5
3 1 2 1 1

4

7 5
1 5 4 3 2 1 1

3

5 10
3 2 5 4 3

3

Hint

[Sample 1 Explanation]

If $\text{Mislav}$ decides to start eating from the $1$-st fruit, then he can eat the $1$-st, $2$-nd, and $4$-th fruits, for a total of $3$ fruits. If he starts from the $2$-nd fruit, then he can eat the $2$-nd, $3$-rd, $4$-th, and $5$-th fruits, for a total of $4$ fruits.

[Constraints]

For $100\%$ of the testdata, $1 \le N \le 1000$, $1 \le C \le 10^6$, $1 \le w_i \le 1000$.

[Source]

Translated from COCI 2015-2016 CONTEST #6 T2 PUTOVANJE.

The score settings follow the original COCI problem, with a full score of $80$.

Translated by ChatGPT 5