Problem1014--「一本通 1.2 练习 1」数列分段 II

1014: 「一本通 1.2 练习 1」数列分段 II

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 8  Solved: 2
Submit Status Web Board

Creator:

Description

对于给定的一个长度为 NNN 的正整数数列 AAA ,现要将其分成 MMM 段,并要求每段连续,且每段和的最大值最小。

例如,将数列 4  2  4  5  14 \ \ 2 \ \ 4 \ \ 5 \ \ 14 2 4 5 1 要分成 333 段:

若分为 [4[4[4 2][42][42][4 5][1]5][1]5][1],各段的和分别为 6,9,16, 9, 16,9,1 ,和的最大值为 999

若分为 [4][2[4][2[4][2 4][54][54][5 1]1]1],各段的和分别为 4,6,64, 6, 64,6,6 ,和的最大值为 666

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

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


Input

111 行包含两个正整数 NNNMMM

222 行包含 NNN 个空格隔开的非负整数 AiA_iAi,含义如题目所述。


Output

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


Sample Input

5 3
4 2 4 5 1

Sample Output

6

HINT

对于 20%20\%20%的数据,有 N≤10N \leq 10N10

对于 40%40\%40% 的数据,有 N≤1000N \leq 1000N1000

对于 100%100\%100%的数据,有 N≤106N \leq 10^6N106M≤NM \leq NMNAiA_iAi 之和不超过 10910^9109


Source/Category


Submit Status