题目描述

给定一个长度为 $N$ 的序列$A$，要求把该序列分成若干段，在满足“每段中所有数的和”不超过$M$ 的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值。

输入格式

第一行包含两个整数 $N$和 $M$。

第二行包含$N$个整数，表示完整的序列 $A$。

输出格式

输出一个整数，表示结果。

如果结果不存在，则输出 −1。

样例

8 17
2 2 2 8 1 8 2 1

12

数据范围

$0≤N≤10^5, 0≤M≤10^{11}$, 序列A中的数非负，且不超过$10^6$

来源

• POJ3017
• 算法竞赛进阶指南