【背景】

义卖所得资金全部捐给智能工厂。工厂接到一笔订单：连续完成 m 个生产任务，任务顺序固定，不能并行、不能拆分，但可以连续分段。现要将这些任务分配给 k 名工人进行生产。每名工人的生产效率相同，一项生产任务不允许分配给两名（或以上）工人同时生产，且分配给每名工人的任务必须是连续的，例如不能把第 1 项、第 3 项、第 4 项任务分配给同一名工人生产。

【任务】

现在请你设计一种任务分配方案，使得完成所有生产任务的总时间最短。这里的总生产时间以生产任务量最多的工人所花费的时间来衡量（假设单位任务量花费单位时间）。

【输入格式】

从文件 work.in 中读取数据。 第一行两个整数 m, k，分别表示生产任务的总项数和参与生产的工人数量。

第二行 m 个整数，第 i 个整数表示第 i 项生产任务所需的任务量（即完成该任务需要花费的时间）。

【输出格式】

输出到 work.out 中。 输出一个整数，代表完成所有生产任务的最短总时间。

【输入输出样例】

样例输入 1

9 3
1 2 3 4 5 6 7 8 9

样例输出 1

17

样例解释：

将 9 项生产任务按以下方式分配给 3 名工人，可使总生产时间最短：

第 1 名工人负责第 1–5 项任务，总任务量为 1+2+3+4+5=15，花费时间 15；

第 2 名工人负责第 6–7 项任务，总任务量为 6+7=13，花费时间 13；

第 3 名工人负责第 8–9 项任务，总任务量为 8+9=17，花费时间 17；

此时生产任务量最多的工人花费时间为 17，即为完成所有生产任务的最短总时间。

【数据范围】

任务项数与工人数量满足 1 ≤ k ≤ m ≤ 500，即工人数量不会超过任务项数，且至少有 1 名工人和 1 项任务。