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.