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

Input

Given N(0 <N’s 100 000), M, and 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 cutting exist output-1.

sample TC1:

N = 8

M = 17

sequence = [2,2,2,8,1,8,2,1]

expected answer: 12

sample TC2:

N = 28

M = 20

sequence = [1,21,4,9,20,6,11,27,12,21,22,16,13,9,1,8,13,10,9,4,11,7,28,9,13,26,17,18]

don’t know expected answer