题目描述

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

例如，将数列$\red{ 4 \ \ 2 \ \ 4 \ \ 5 \ \ 1}$ 要分成 $\red{3}$ 段：

若分为 $\red{[4 ~2][4~ 5][1]}$，各段的和分别为 $\red{6, 9, 1}$ ，和的最大值为 $\red{9}$；

若分为 $\red{[4][2~ 4][5~ 1]}$，各段的和分别为 $\red{4, 6, 6}$ ，和的最大值为 $\red{6}$；

并且无论如何分段，最大值不会小于 $\red{6}$。

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

输入格式

第 $\red{1}$ 行包含两个正整数 $\red{N}$，$\red{M}$；

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

输出格式

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

样例

输入样例

5 3
4 2 4 5 1

输出样例

6

提示

对于 $\red{20\%}$的数据，有 $\red{N \leq 10}$；

对于 $\red{40\%}$的数据，有 $\red{N \leq 1000}$；

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