题目描述

给定一个长度为 $N$ 的非负整数序列 $A_1, A_2, \dots, A_N$。要求把该序列分成若干连续段，使得每一段内所有数之和不超过 $M$，并且使得各段内的最大值之和最小。

试计算这个最小值。

输入格式

• 第一行两个整数 $N$ 和 $M$。
• 第二行 $N$ 个整数，表示序列 $A$。

输出格式

• 一个整数，表示最小的“每段内最大值之和”。
• 如果无法按条件分段（例如某一段一个数就大于 $M$），则输出 $-1$。

数据范围

• $0 \le N \le 10^5$
• $0 \le M \le 10^{11}$
• $0 \le A_i \le 10^6$（非负整数）

输入样例

8 17
2 2 2 8 1 8 2 1

输出样例

12

样例解释

$N=8, M=17$
序列：$[2, 2, 2, 8, 1, 8, 2, 1]$

我们需要将序列分成若干连续段，每段和 $\le 17$，并使各段的最大值之和最小。

一种可行的划分：

• 第 1 段：$[2, 2, 2, 8, 1]$
  和 $= 2+2+2+8+1 = 15 \le 17$，最大值是 $8$。
• 第 2 段：$[8, 2, 1]$
  和 $= 8+2+1 = 11 \le 17$，最大值是 $8$。
  总和 $= 8 + 8 = 16$。

但 16 不是最优。

尝试更优划分：

• 第 1 段：$[2, 2, 2]$
  和 $= 6$，最大值是 $2$。
• 第 2 段：$[8, 1, 8]$
  和 $= 8+1+8=17$，最大值是 $8$。
• 第 3 段：$[2, 1]$
  和 $= 3$，最大值是 $2$。
  总和 $= 2 + 8 + 2 = 12$。

12 比 16 更小，且各段和都不超过 17。
事实上，12 是最小值（可以验证没有更小的方案）。

为什么不是更小？
例如如果想让第 2 段的最大值变小，必须把两个 8 分开，但分开后可能使得其他段的和超过 17，或者段数变多导致总和变大。
最优策略是尽量让大的数单独成段，或者与比它小的数一起成段，以减少对后续段的影响，同时保证每段和不超限。

输出：$12$