P1182 数列分段 Section II

题目描述

对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\le N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4 2 4 5 1 要分成 3 段，按照如下方式划分：

{4 2}{4 5}{1}

得到的最大一段和为 9，在这种分法中是平均值最小的。

按照如上方式，将每一段分别求和，并取所有段和中最大的那个，求该值的最小可能是多少。

输入格式

第 1 行包含两个正整数 $N$，$M$。

第 2 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

输入输出样例

input1

5 3
4 2 4 5 1

output1

9

说明/提示

对于 $100\%$ 的数据，保证 $1\le N\le 10^5$，$1\le M\le N$，$0\le A_i\le 10^4$。