Background

POJ3017

Description

给定一个长度为N的序列A，要求把该序列分为若干段，在满足“每段中所有数的和”不超过M的前提下，让“每段中所有数的最大值”之和最小。 试计算这个最小值，N≤10^5，数列A中的数非负，且不超过10^6，M≤10^11

Format

Input

分别是N，M和N个数

Output

输出最小值

Samples

8 17
2 2 2 8 1 8 2 1

12

Others

对于30%的数据：N≤50

对于50%的数据：N≤100

对于70%的数据：N≤1000

对于100%的数据：N≤10^5，数列A中的数非负，且不超过10^6，M≤10^11