题目描述

给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \ldots, A_N$，需要将其切分成恰好 $M$ 段连续的子序列（每段非空）。定义一种切分方案的代价为所有子序列和的最大值。求所有合法切分方案中，代价的最小值。

输入格式

第一行两个正整数 $N$ 和 $M$。

第二行 $N$ 个正整数，表示序列 $A$。

输出格式

输出一个正整数，表示代价的最小值。

样例

5 3
4 2 4 5 1

6

提示

$1 \le N \le 10^5$，$1 \le M \le N$，$1 \le A_i \lt 10^8$，答案不超过 $10^9$。