题目描述
飞船的智能安全系统给出了这样一个问题：
有一个长度为n的正整数数列a1~an，现要将其分成m（m≤n）段，并要求每段连续，并且每段和中的最大值最小。
例如数列a = 4 2 4 5 1，现在要分成3段。
一种方案是：[4 2]，[4 5]，[1]
这时第一段和为6，第2段和为9，第3段和为1，每段和的最大值为9。
还有一种方案是：[4]，[2 4]，[5 1]
这时第一段和为4，第2段和为6，第3段和为6，每段和的最大值为6。
当然还有其他的方案，但是无论如何分段，每段和的最大值都不会小于6。
所以最终的结果就是6。
输入
第1行包含两个正整数n,m。
第2行包含n个空格隔开的非负整数ai，含义如题目所述。
1≤n≤100000，m≤n，ai < 10^8
输出
一个整数，表示答案，答案不超过10^9。
样例输入
5 3
4 2 4 5 1样例输出
6