Minimum Bookshelf Width

We are given a sequence of (n) books arranged in a specific order. The (i)-th book has a length (h_i). You need to place all these books onto a bookshelf that has several layers. The following conditions must be met for each layer:

1. The books on each layer must be consecutive in the original sequence.
2. The sum of the lengths of the books on each layer does not exceed a given parameter (m).
3. The width of a layer must be at least as large as the length of every book placed on that layer. In order to minimize the total bookshelf width, you should set the width of a layer equal to the maximum book length in that layer.

The total width of the bookshelf is the sum of the widths of all layers. Your task is to determine the minimum possible total bookshelf width.

Mathematical Formulation:

Let the books be partitioned into segments (layers) ( [a_1,b_1], [a_2,b_2], \ldots, [a_k,b_k] ) such that for each segment, (\sum_{i=a_j}^{b_j} h_i \le m) and the cost of the segment is (\max_{i=a_j}^{b_j} h_i). We need to choose the segmentation which minimizes the total cost [ \text{Total Width} = \sum_{j=1}^{k} \max_{i=a_j}^{b_j} h_i. ]

inputFormat

The first line contains two integers (n) and (m) where (n) is the number of books and (m) is the maximum allowed sum of book lengths on one shelf.

The second line contains (n) integers (h_1, h_2, \dots, h_n), where (h_i) denotes the length of the (i)-th book.

outputFormat

Output a single integer, the minimum total width of the bookshelf.

sample

5 10
3 2 5 4 1

9