题目背景

Sanhai 的 OJ 最近老是崩。日志里全是“峰值负载过高”的提示：大量提交冲进来，服务器的处理负载在某个时间段里飙到阈值之上，系统就挂了。于是乎， Sanhai 决定加一个“断路器”：当负载即将超过阈值时，立刻触发一次“冷重启”（短暂停机清空队列，再继续处理），但重启次数太多又会拖慢整体效率。

他想要一个平衡点：在允许的重启次数范围内，选择一个尽可能低的服务器容量阈值，让系统全程不崩。（hahhahah)

题目描述

给定一个长度为 $n$ 的非负整数序列，表示连续到达的任务负载量。系统以顺序处理的方式运行，设定一个容量阈值 $C$，当某一段连续处理的总负载超过 $C$ 时，系统会崩溃。你可以在处理过程中插入至多 $b$ 次$“$冷重启$”$，每次重启会将当前段的累积负载清零，然后继续处理剩余任务。

请你在最多 $b$ 次重启的前提下，求出能够保证系统不崩溃的最小容量阈值 $C$。

等价地：将序列分割成至多 $b+1$ 段，使每一段的元素和不超过 $C$；要求 $C$ 尽可能小。

输入格式

• 第一行两个整数 $n$, $b$。
• 第二行 $n$ 个非负整数 $a_1, a_2, ..., a_n$，表示每个任务的负载量。

输出格式

• 输出一个整数 $C$，表示在最多 $b$ 次重启下使系统不崩的最小容量阈值。

说明与细节

• 重启发生在段与段的边界处，重启后累积清零。
• 任意单个任务的负载量不能超过容量阈值；否则无论如何都会崩溃。
• 你可以选择不使用全部重启次数（使用次数 $≤ b$）。
• 要保证所有任务按顺序全部被处理。

数据范围

• $1 ≤ n ≤ 2 × 10^5$
• $0 ≤ b ≤ n − 1$
• $0 ≤ a_i ≤ 10^9$
• 答案 C 的范围在 $[max(ai), sum(ai)]$，建议使用 64 位整型。

样例一

输入：

5 1
7 2 5 10 8

输出：

18

解释：

• 最优做法是将序列划分为两段（b = 1 次重启，最多分成 2 段）：
  • 段1：7, 2, 5，和为 14
  • 段2：10, 8，和为 18
• 所需容量阈值 $C = 18$；无法做到更小（例如 $C = 17$ 会使第二段超限）。

样例二

输入：

6 2
3 3 3 3 3 3

输出：

9

解释：

• 至多 $2$ 次重启，最多分 $3$ 段。最佳为 $3$ 段，每段 $3+3+3 = 9$。
• 若 $C < 9$，则任一段至少包含三个 $3$ 的情况下会超限，不可行。

提示

• 可以对 C 进行二分搜索，在每次判定中用贪心地“尽量装满当前段”的方式统计需要的段数。如果段数 $≤ b+1$，则该 C 可行；否则不可行。
• 判定时：
  • 若存在 $a_i > C$，则直接不可行。
  • 否则从左到右累加，超过 C 就开新段计数。
• 时间复杂度约为 $O(n$ $log$ $sum(a_i))$，需使用 64 位整型存储累加和与答案。