问题1689--每月支出

1689: 每月支出

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

给出n天中每天的花费，需要将这些天分成m组，每组包含连续的一或多天，若定义第i组的花费为K，求一种分组方法使得K=max{Ki}最小。


输入

第一行为两个正整数N和M，之后输入N个正整数，分别表示第i天的花费。

输出

包含一行，表示上面描述的K。

样例输入 Copy 

7 5
100
400
300
100
500
101
400

样例输出 Copy 

500

提示

1 ≤ n ≤ 100,000
1 ≤ m≤ n
1 ≤ Ki≤ 10,000

来源/分类

分治算法 
[提交] [状态]