#3422. 裁剪序列 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

试计算这个最小值。

输入格式

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

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

输出格式

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

如果结果不存在,则输出-1。

样例

样例输入

8 17
2 2 2 8 1 8 2 1

样例输出

12

数据范围与提示

,

,

POJ 3017