## Description

Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.## Input

The first line of input contains two integer N (0 < N ¡Ü 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.## Output

Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output -1.## Sample Input

8 17 2 2 2 8 1 8 2 1## Sample Output

12## Hint

Use 64-bit integer type to hold M. (long long)## Author

POJ Monthly--2006.09.29, zhucheng