Description

You are given, in a fixed order, all the books to be placed on the bookshelf. There are $n$ books, and the $i$-th book has a length $h_i$.

The bookshelf has several layers (shelves). The widths of different layers may vary, but the width of a layer cannot be smaller than the length of any book placed on that layer. At the same time, the sum of the lengths of the books on each layer cannot exceed a given parameter $m$, and the books on any layer must be a contiguous subsequence in the given order.

The width of the bookshelf is the sum of the widths of all layers. Find the minimum possible width of the bookshelf.

Input Format

The first line contains two integers $n$ and $m$.

From line $2$ to line $(n + 1)$, each line contains one integer. The integer on line $(i + 1)$ is the length $h_i$ of the $i$-th book.

Output Format

Output a single integer on one line representing the answer.

4 6
1
3
3
1

5

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \leq 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq h_i \leq 10^9$, $\max\limits_{i = 1}^{n} h_i \leq m \leq 10^9$.

Hint

Because the original statement was quite ambiguous, here is a simplified version:

Given a sequence $h$ of length $n$, partition $h$ into several segments such that the sum of numbers in each segment does not exceed $m$, and minimize the sum of the maximum values of all segments.

Translated by ChatGPT 5