题目描述

给定一个长度为$N$的整数序列$\{a_n\}$，你需要将这个序列分成若干部分，每一部分都是原序列中连续的子序列。且每一部分需要满足：该部分中所有整数的和不超过给定的整数$M$。你需要找到一种分割方式，使得每一部分的最大值之和最小。

输入格式

第一行输入包含两个整数$N$（$0 < N \leq 100\,000$）和$M$。
接下来一行包含$N$个整数，描述这个整数序列。序列中的每个整数都在$0$到$1\,000\,000$之间（包含$0$和$1\,000\,000$）。

输出格式

输出一个整数，表示每一部分的最大值之和的最小值。如果不存在这样的分割方式，则输出$-1$。

样例输入 1

8 17
2 2 2 8 1 8 2 1

样例输出 1

12

提示

使用$64$位整数类型来存储$M$。

来源

POJ Monthly--2006.09.29, zhucheng