题目描述

对于给定的一个长度为 \(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 \leq 10\)；

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

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