数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列$A-i$,现要将其分成$M(M≤N)$段,并要求每段连续,且每段和的最大值最小。 关于最大值最小: 例如一数列$4 2 4 5 1$要分成$3$段 将其如下分段: $[4 2][4 5][1]$ 第一段和为$6$,第$2$段和为$9$,第$3$段和为$1$,和最大值为$9$。 将其如下分段: $[4][2 4][5 1]$ 第一段和为$4$,第$2$段和为$6$,第$3$段和为$6$,和最大值为$6$。 并且无论如何分段,最大值不会小于$6$。 所以可以得到要将数列$4 2 4 5 1$要分成$3$段,每段和的最大值最小为$6$。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

5 3
4 2 4 5 1

输出样例 #1

6

说明

对于$20\%$的数据,有$N≤10$; 对于$40\%$的数据,有$N≤1000$; 对于$100\%$的数据,有$N≤100000,M≤N, A_i$之和不超过$10^9$。