小明的花费预算

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小明终于找到一份工作了,但是老板是个比较奇怪的人,他并不是按照每月每月的这样发工资,他觉得你想什么时候来取都可以,而小明恰好是一个花钱比较大手大脚的人,所以他希望每次取得钱正好够接下来的n个月的花费,以防浪费。
小明很懒,懒到他连钱都尽量不愿多带(只是嫌沉)。但是他在只有m次取钱的机会,所以他想要用m次把n个月的钱都取出来,但想要每次都尽量少取些。给你小明n个月的花费,还有可取的次数m,问小明在保证每次尽量少取些钱的情况下,最多的那次取了多少钱?当然,每次取钱只能取连续几个月的花费。

Input

多组输入。
第一行是两个整数,n(1 ≤ n ≤ 100,000)和m (1 ≤ m ≤ n)
接下来的n行是连续n个月的花费,第i+1行是第i个月的花费。

Output

 输出满足最大的总花费最小的那个组的总花费。

Sample Input

5 3
3
2
9
4
1

Sample Output

9

Hint

 将5个月分为3组,第一组(3,2),第二组(9),第三组(4,1),第二组的总花费最大为9,若按其他的方式分,花费最大的那一组的总花费将>=9.

Source

lwn