题目描述

对于给定的一个长度为 \(N\) 的正整数数列 \(A\)，现要将其分成 \(M\) 段，并要求每段连续，且每段和的最大值最小。

例如，将数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段：

若分为 \([4\ 2][4\ 5][1]\)，各段的和分别为 \(6, 9, 1\)，和的最大值为 \(9\)；

若分为 \([4][2\ 4][5\ 1]\)，各段的和分别为 \(4, 6, 6\)，和的最大值为 \(6\)；

并且无论如何分段，最大值不会小于 \(6\)。

所以可以得到要将数列 \(4\ 2\ 4\ 5\ 1\) 分成 \(3\) 段，每段和的最大值最小为 \(6\)。

---

输入格式

第 \(1\) 行包含两个正整数 \(N\)、\(M\)；

第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。

---

输出格式

仅包含一个正整数，即每段和最大值最小为多少。

---

样例

输入

5 3
4 2 4 5 1

输出

6

---

数据范围与提示

对于 \(20\%\) 的数据，有 \(N \le 10\)；

对于 \(40\%\) 的数据，有 \(N \le 1000\)；

对于 \(100\%\) 的数据，有 \(N \le 10^5\)，\(M \le N\)，\(A_i\) 之和不超过 \(10^9\)。