Description

Given a sequence $A_i$ of length $N$ consisting of non-negative integers, split it into several consecutive segments such that the sum of each segment does not exceed $M$ (it can be equal to $M$). Find the minimum number of segments needed to meet the requirement.

Input Format

The first line contains two positive integers $N, M$, representing the length of the sequence $A_i$ and the maximum allowed sum of each segment. The second line contains $N$ space-separated non-negative integers $A_i$, as described.

Output Format

Output a single integer: the minimum number of segments.

5 6
4 2 4 5 1

3

Hint

For $20\%$ of the testdata, there is $N≤10$.

For $40\%$ of the testdata, there is $N≤1000$.

For $100\%$ of the testdata, there are $N≤100000, M≤10^9$, $M$ is greater than the maximum element, and the sum of $A_i$ does not exceed $10^9$.

Split the sequence as follows:

$[4][2 4][5 1]$

The sum of the first segment is $4$, the sum of the $2$nd segment is $6$, and the sum of the $3$rd segment is $6$, all not exceeding $M=6$. It can be proven that $3$ is the minimum number of segments.

Translated by ChatGPT 5