该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D-切分数列（split）

题目背景

小 A 正在研究如何把一列数字合理地分组。

他希望把一个长度为 $n$ 的数列切成若干段，每一段都必须是 连续的一段 ，并且所有段都不能为空。为了让每一段的 压力 尽量均衡，他想让 每一段的元素和的最大值尽可能小 。

你的任务是帮助他求出这个最优值。

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$，请你将它划分成 恰好 $k$ 个非空连续子段 。

设这 $k$ 个子段的元素和分别为：

你需要最小化：

输出这个最小值。

输入格式

第一行输入两个整数 $n,k$，分别表示数列长度和需要划分的连续子段个数。

第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数，表示把数列划分成恰好 $k$ 个非空连续子段后，各段元素和最大值的最小可能值。

输入输出样例

输入 #1

5 3
7 2 5 10 8

输出 #1

14

样例解释

一种最优划分方式是：

三段的段和分别为：

因此这一种划分下，最大段和为：

可以证明，不存在一种划分方案，使得最大段和小于 $14$。

数据范围

对于所有测试数据，保证：$1 \le k \le n \le 2 \times 10^5,\quad 1 \le a_i \le 10^9$

本题共设 $20$ 个测试点，各测试点满足的限制如下：

特殊性质 $A$：保证 $k=1$。

特殊性质 $B$：保证 $k=n$。

特殊性质 $C$：保证数列单调不降，即对任意 $1 \le i < n$，都有 $a_i \le a_{i+1}$。

特殊性质 $D$：保证所有 $a_i$ 相等。

特殊性质 $E$：保证 $a_i \le 1000$。