2056: 宝典2第一章花费

【题目描述】花费（Expense.cpp/c/pas）POJ 3273

邪狼发愁的说：“这么高级的车怎么就断轴了？”

修罗王一脸的郁闷：“是啊，当时厂家还信誓旦旦的拍胸脯说这车经过魔法加强处理的。这加两块木板也算？没办法，剩下的路程只好走路了。”

邪狼摸摸钱袋，说：“好像钱也没多少了。”

已知修罗王和邪狼的逃亡天数为N(1 ≤N≤100000)，每天需要花的钱已经分配好，请把这些天分成M(1≤M≤N)份（每份都是连续的天），则第i段的和为sum[i]（i=1，2，…，M），求max{sum[i]}最小为多少？

【输入格式】

第一行为两个整数即Ｎ和Ｍ。第二行为Ｎ个数。

【输出格式】

输出分成Ｍ份后的最小和。

【输入样例】

7 5（表示N=7，M=5）

200 300 300 200 500 221 420  (表示每天的花费)

【输出样例】

500