P10977 Cut the Sequence

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.

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 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$.

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