测试数据来自 wjszez/2823

题目描述
方糕的轮椅又丢了！众所周知，方糕的腿伤及其严重，日常生活必须依赖他宝贵的轮椅。然而，总有一些人，比如那个狡猾的巨魔ywf，他们不怀好意，总是喜欢找方糕的麻烦，甚至故意把他的轮椅藏起来。这次巨魔ywf向方糕发起了挑战，如果他能在最小时间内找回他的轮椅，那他承诺以后再也不会捉弄方糕而且会把他的零食与方糕分享，方糕听闻后毅然决然接受了挑战，当然并不是为了巨魔ywf的零食。
Just as the saying goes：上帝给他关上了一扇门，也给他打开了一扇窗，方糕会使用影分身术来寻找轮椅，但他只能分出m个分身寻找，这里有n个房间，每个房间都有可能出现轮椅，当然还有假的轮椅，因此方糕要把每个房间都搜一遍，他将n个房间分为m块，每个分身搜索一块区域，搜索第i个房间需要ti分钟，总的搜索时间为每块区域的时间和的最大值。请你帮助方糕摆脱巨魔ywf的骚扰，求出最小的搜索时间。
解释：例如一数列 4 2 5 1要分成 3 段。
将其分为（4）（2 4）（5 1）
第一段和为 4，第 2段和为 6，第 3 段和为 6，搜索时间为 6。

输入格式
第一行包含两个正整数n,m
第二行包含n个空格隔开的非负整数ti，含义如题目所述。

输出格式
一个正整数，即最小的搜索时间。
输入输出样例
输入
5 3
4 2 4 5 1
输出
6

数据范围
对于20%的数据，n<=10
对于40%的数据，n<=1000
对于100%的数据，1<=n<=10^5,m<=n,ti<10^8
##N/A