#P1182. 数列分段 Section II

数列分段 Section II

题目描述

对于给定的一个长度为 NN 的正整数数列 A1NA_{1\sim N},现要将其分成 MMMNM\leq N)段,并要求每段连续,且每段和的最大值最小。

关于最大值最小:

例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段。

将其如下分段:

[4 2][4 5][1][4\ 2][4\ 5][1]

第一段和为 66,第 22 段和为 99,第 33 段和为 11,和最大值为 99

将其如下分段:

[4][2 4][5 1][4][2\ 4][5\ 1]

第一段和为 44,第 22 段和为 66,第 33 段和为 66,和最大值为 66

并且无论如何分段,最大值不会小于 66

所以可以得到要将数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段,每段和的最大值最小为 66

输入格式

11 行包含两个正整数 N,MN,M

22 行包含 NN 个空格隔开的非负整数 AiA_i,含义如题目所述。

输出格式

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

5 3
4 2 4 5 1
6

提示

对于 20%20\% 的数据,N10N\leq 10

对于 40%40\% 的数据,N1000N\leq 1000

对于 100%100\% 的数据,1N1051\leq N\leq 10^5MNM\leq NAi<108A_i < 10^8, 答案不超过 10910^9