题目描述

给出一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$，以及一个整数 $m$。

现在要把这个序列划分成恰好 $m$ 个连续的非空段。设第 $i$ 段的和为 $s_i$，定义这种划分的代价为 $\max\{s_1,s_2,\dots,s_m\}$。

请求出所有划分方案中代价的最小值。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数，表示最小代价。

输入输出样例 #1

输入 #1

5 3
4 2 4 5 1

输出 #1

6

说明

数据范围

• 对于 $100\%$ 的数据，$1\le m\le n\le 10^5$，$1\le a_i\le 10^4$。若能用不超过 $m$ 段覆盖。