#10014. 「一本通 1.2 练习 1」数列分段 II

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

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

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

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

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

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

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

输入格式

1 行包含两个正整数 N M

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

输出格式

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

样例

样例输入

5 3
4 2 4 5 1

样例输出

6

数据范围与提示

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

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

对于 100\% 的数据,有 N \leq 10^5 M \leq N A_i 之和不超过 10^9