Description

现按一定顺序给出所有要放置于书架上的书，共有 $n$ 本，第 $i$ 本书有一个长度 $h_i$。

书架有若干层，层与层之间的宽度不一定相等，但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时，每层上的书的长度之和不能超过一个给定的参数 $m$，且任何层上的书必须是给出的书的序列中连续的几本。

书架的宽度是所有层的宽度之和，求书架的最小宽度。

Input Format

输入的第一行包含两个整数 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 本书的长度 $h_i$。

Output Format

输出一行一个整数表示答案。

4 6
1
3
3
1

5

Hint

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \leq 10^3$。
• 对于 $100\%$ 的数据，保证 $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$。

提示

由于原题题意严重模糊不清，现给出简化版题意：

给出一个长度为 $n$ 的序列 $h$，请将 $h$ 分成若干段，满足每段数字之和都不超过 $m$，最小化每段的最大值之和。