时间限制：1秒　　内存限制：256M

---

【问题描述】

　　把长度为 \(n\) 的正整数的序列划分成 \(m\) 个非空连续子序列，使得每个正整数恰好属于一个序列。设第 \(i\) 个序列各数之和为 \(S(i)\)，你的任务是让所有 \(S(i)\) 的最大值尽量小。
　　例如：序列 1 2 3 2 5 4 划分成 3 个连续子序列的最优方案是 1 2 3|2 5|4，其中 \(S(1)=6、S(2)=7、S(3)=4\)，最大的 \(S(i)\) 为7；如果划分成1 2|3 2|5 4，其中 \(S(1)=3、S(2)=5、S(3)=9\)，最大的 \(S(i)\) 为9，不如刚才的好。

【输入格式】

　　输入两个用空格隔开的正整数 \(n\) 和 \(m\)。以下 \(n\) 行每行一个正整数，表示序列的每个元素。

【输出格式】

　　输出最大的 \(S(i)\) 的最小值。

【输入输出样例】

　Input

7 5
100 400 300 100 500 101 400

　Output

500

【数据限制】

　　\(100\%\) 的数据：\(1≤n≤100000 ，m≤n\)，序列中的数是不超过 \(10000\) 的正整数。

【来源】

　　Mr.he