3873: 星际怪兽（monsters）

monsters.in/monster.out
小 D 和小 T 玩了好几轮纸牌游戏后，小 T 觉得受伤害的总是自己，于是他决定不跟小 D 玩了，小 D 为了安抚小 T 受伤的心灵，给小 D 讲了一个他在潘多拉星球遇到怪兽的故事：潘多拉星球有一种不死怪兽，长得豹头蛇身，异常凶残。被人砍断身体后，会从残体里最大的一块重新长出完整的身体，残体越大生长速度就越快，怪物在生长 期间是没有攻击力的。怪兽的身体分为 n 个部分，只有在两个不同身体部分的交接的处才能砍断怪兽，幸好我们的小 D 带着上古神剑轩辕剑，但轩辕剑只能砍怪兽 k 次就 报废了，当然轩辕剑好歹是上古名剑，一次就能把怪兽一剑两断，为了获得足够的逃跑时间，小 D 需要砍了 k 剑后，怪兽残体最大的一块尽量小，这样他就能获得更多的 逃跑时间。当然聪明的小 D 能够安全到达地球，说明他并没有被怪兽吃掉，现在他想考下小 T，怎样砍怪兽才能获得最多的逃跑时间？ 




【样例解释】 砍了四剑后怪物分成了 100+400，300+100,500,101，400 五段，怪兽会从第一段或者第三段重生。 




【数据范围】 对于 40%的数据满足：a[i]<=100,0<=k

第一行输入两个正整数 n, k。n 表示怪兽身体分成几部分,k 表示轩辕剑可以砍 k次。 第二行输入 n 个由空格隔开的正整数 ，表示怪兽从头到尾每个身体部分的体积。

输出一个整数表示怪物被砍后，小 D 获得最多逃跑时间时怪物残体最大的体积。

7 4
100 400 300 100 500 101 400

500