给一个序列$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$。