题目描述

给定一个长度为 $N$ 的整数序列 $\{a_N\}$，你需要将这个序列切分成若干部分，每一部分都是原序列的一个连续子序列。每部分必须满足部分内的整数之和不超过给定的整数 $M$。你的任务是找到一种切分方式，使得每一部分的最大整数之和最小化。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$0 < N \leq 100000$，$M$ 是 int 范围内的正整数）。接下来的第二行包含 $N$ 个整数，描述了整数序列。序列中的每个整数都在 $0$ 到 $1000000$ 之间（含 $0$ 和 $1000000$）。

输出格式

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

8 17
2 2 2 8 1 8 2 1

12