题目描述

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

试计算这个最小值。

输入格式

第一行包含两个整数$\red {N}$和$\red {M}$。

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

输出格式

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

如果结果不存在，则输出$\red {-1}$。

样例

输入样例

8 17
2 2 2 8 1 8 2 1

输出样例

12

提示

$\red {0≤N≤105}$,

$\red {0≤M≤1011}$,

序列$\red {A}$中的数非负，且不超过$\red {106}$