P7798 [COCI 2015/2016 #6] PUTOVANJE

$\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?

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 one integer, the maximum number of fruits that $\text{Mislav}$ can eat.

**[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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T2 PUTOVANJE**. **The score settings follow the original COCI problem, with a full score of $80$**. Translated by ChatGPT 5