题目内容

要把一个神经网络的 $N$ 个层切到 $K$ 块 GPU 上做流水线并行。切完后每一段叫做一个 Stage，训练时按 Stage 顺序接力计算。

一个 Stage 的负载等于它包含的各层前向传播时间之和。若 Stage $s$ 覆盖连续层 $l_1,\dots,l_t$，则

其中 $f[i]$ 是第 $i$ 层的前向时间。流水线由最慢的 Stage 卡住，因此要最小化所有 Stage 负载的最大值。

切分必须同时满足：

1. 每个 Stage 内的层编号连续
2. 每一层恰好属于一个 Stage
3. 每个 Stage 至少含一层

输入描述

第一行两个整数 $N$、$K$，依次为层数和 Stage 个数。

第二行 $N$ 个整数 $f[0]\ f[1]\ \dots\ f[N-1]$，表示各层前向时间（毫秒）。

输出描述

输出一行一个整数，即最小化后的最大 Stage 负载。

约束条件

• $1 \le K \le N \le 5000$
• $1 \le f[i] \le 1000$

样例1

输入：

7 3
4 6 3 8 2 5 4

输出：

11

解释：

只有这一种划分能把峰值压到 $11$。

样例2

输入：

4 2
2 8 3 5

输出：

10

解释：

四层耗时为 $[2,8,3,5]$，要切成 $2$ 个 Stage。

最优为方案 B，峰值负载 $10$。