Minimize Sum of Segment Maximums

Given an integer sequence of length N denoted by \(\{a_i\}_{i=1}^{N}\), you are required to partition the sequence into several contiguous subarrays such that the sum of the integers in each subarray does not exceed \(M\). In all valid partitions, let the value of a partition be the sum of the maximum element from each subarray. Your task is to find the minimum possible value among all valid partitions.

Note: It is guaranteed that each individual element is not greater than \(M\), so that at least one valid partition exists.

inputFormat

The first line contains two integers \(N\) and \(M\), where \(N\) is the number of elements in the sequence and \(M\) is the maximum allowed sum for each segment.

The second line contains \(N\) integers, representing the elements of the sequence \(a_1, a_2, \dots, a_N\>.

outputFormat

Output a single integer representing the minimum possible sum of the maximums of each segment among all valid contiguous partitions.

sample

5 10
2 5 1 3 4

9