Problem Description

Given an integer sequence $\{a_N\}$ of length $N$, you need to split this sequence into several parts such that each part is a contiguous subsequence of the original sequence, and the sum of integers in each part does not exceed $M$. Your task is to find, among all valid splitting ways, the minimum possible value of the sum of the maximum value of each part.

Input Format

The first line contains two integers $N$ and $M$ ($1 \le N \le 10^5$, $1 \le M < 2^{31}$). The second line contains $N$ integers $a_1,a_2,\dots,a_N$ ($0 \le a_i \le 10^6$).

Output Format

Output one integer, which is the minimum possible value of the sum of the maximum value of each part. If there is no valid splitting way, output $-1$.

8 17
2 2 2 8 1 8 2 1

12

Hint

Sample explanation:

Split the sequence into three parts: $\{2,2,2\},\{8,1,8\},\{2,1\}$. Then the sum of the maximum value of each part is $2+8+2=12$. It can be proven that there is no better solution.

Translated by ChatGPT 5