书架

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

按给定顺序有 $n$ 本书，第 $i$ 本书的长度为 $h_i$。你需要把整个序列划分成若干个非空连续段，每个连续段对应书架的一层。

每层中所有书的长度之和不能超过 $m$，这一层的宽度等于该段中书的最大长度。整个书架的宽度等于所有层宽度之和。

求书架宽度的最小可能值。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含一个整数 $h_i$。

输出格式

输出一行一个整数，表示最小宽度。

样例输入

4 6
1
3
3
1

样例输出

5

数据范围

保证 $1\le n\le 10^5$，$1\le h_i\le 10^9$，且 $\max h_i\le m\le 10^9$。