当前没有测试数据。

题目描述

农夫约翰是一个惊人的会计奇才，他已经意识到他可能会耗尽经营农场的资金。他已经计算并记录了在接下来的N (1 ≤ N ≤ 100000)天中每天需要花费的确切金额(1 ≤ moneyi ≤ 10000)。 FJ想为一系列M (1 ≤ M ≤ N)个财政周期创建一个预算，称为“fajomonths”。这些fajomonths中的每一个都包含一组连续的一天或多天。每一天都恰好包含在一个fajomonth中。 FJ的目标是安排一个月的开销，使开销最高的一个月的开销最小，从而确定他的每月开销限额。

输入格式

第1行:两个空格分隔的整数:N和M 第2行..N+1:第i+1行包含农民约翰在第i天花费的美元数 输出

输出格式

第一行:农民约翰可以承受的最小月限额。

样例 #1

样例输入 #1

7 5
100
400
300
100
500
101
400

样例输出 #1

500

提示

如果农民约翰安排月份，使得前两天是一个月，第三和第四天是一个月，最后三天是他们自己的月份，那么他在任何一个月最多花费500美元。任何其他的计划方法都会给出一个更大的最小月限额。

来源

USACO 2007年三月银奖