题目描述

给定一个长度为 $N$ 的非负整数数列：

现在需要将这个数列划分为恰好 $M$ 段，并满足：

• 每一段都不能为空；
• 每一段中的元素在原数列中必须连续。

对于一种划分方案，计算每一段的元素和，并取这些段和中的最大值。

请你找到一种划分方案，使得这个最大值尽可能小，并输出这个最小值。

例如，对于数列：

将其划分为 $3$ 段。

若划分为：

则三段的和分别为 $6$、$9$、$1$，其中最大值为 $9$。

若划分为：

则三段的和分别为 $4$、$6$、$6$，其中最大值为 $6$。

并且不存在一种划分方式，使得最大段和小于 $6$，因此答案为 $6$。

输入格式

第一行输入两个正整数 $N$、$M$，分别表示数列长度和需要划分的段数。

第二行输入 $N$ 个非负整数 $A_1,A_2,\ldots,A_N$，表示给定数列。

输出格式

输出一个整数，表示将数列划分为 $M$ 个连续非空段后，能够得到的最小最大段和。

样例

5 3
4 2 4 5 1

6

数据范围

对于 $20\%$ 的测试数据：

$N \le 10$。

对于 $40\%$ 的测试数据：

$N \le 1000$。

对于 $100\%$ 的测试数据：

$1 \le N \le 10^5$。

$1 \le M \le N$。

$0 \le A_i < 10^8$。

答案不超过 $10^9$。

来源：洛谷P1182