给一个序列$a_1, a_2, \dots, a_n$。
你想把这个序列划分成$k$段,对于每一段求和,希望这$k$段的和里面最小值最大。问这个值是多少。
输入格式
第一行两个整数$n, k$。接下来一行$n$个整数,表示$a_1, a_2, \dots, a_n$。
输出格式
输出一行,一个整数,表示答案。
样例输入1
5 3
1 4 2 6 8
样例输出1
6
样例解释
划分成1 4 2 | 6 | 8
这么三段。
数据规模
对于$100\%$的数据,满足$1\leq k\leq n\leq 10^5, 1\leq a_i\leq 10^8$。