题目描述

给定一个长度为 $N$ 的整数序列 $\{a_N\}$，你需要将这个序列划分成若干部分，满足每一部分都是原序列的一个连续子序列，且每个部分的整数之和均不超过 $M$。你的任务是求出在所有合法的划分方式中，每一部分的最大值之和的最小值。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 10^5$，$1\le M < 2^{31}$）。第二行包含 $N$ 个整数，依次为 $a_1,a_2,\dots,a_N$（$0\le a_i\le 10^6$）。

输出格式

输出一个整数，表示每一部分的最大值之和的最小值。如果不存在合法的划分方式，输出 $-1$。

8 17
2 2 2 8 1 8 2 1

12

提示

样例解释：

将序列划分为三个部分：$\{2,2,2\},\{8,1,8\},\{2,1\}$，此时每一部分的最大值之和为 $2+8+2=12$。可以证明，不存在更优的方案。