小明找到了一份临时工作,渴望挣得一些零用钱。从今天起,小明将连续工作N天(1<=N<=100 000)。每一天结束时他可以领取当天及前面若干天里没有领取的工资,但他总共只有M(1<=M<=N)次领取工资的机会。小明已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱,他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意小明必须恰好领工资M次,且需要将所有的工资全部领走(即最后一天结束时需要领一次工资)。
【输入格式】
第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数,依次表示每一天的薪水。
【输出格式】
输出领取到的工资的最大值最小是多少。
【输入样例】
7 5
100
400
300
100
500
101
400
输出样例】
500
【样例说明】
采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。
100 400 300 100 500 101 400 每一天的薪水
<------1 <-------2 <---3 <---4 <---5 领取工资的时间
500 400 500 101 400 领取到的工资