题目描述

有一个长度为 $n$ 的整数序列 $a_1 \ldots a_n$（$a_i$ 可以为负数）。将它们分成正好 $m$ 段。设第 $i$ 段的子序列和为 $s_i$（$i \in [1, m]$）。求一个拆分方法，使 $\max_{i=1}^m\{s_i\}$ 最小。

输入格式

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

接下来 $n$ 个整数，代表 $a_1 \ldots a_n$。

输出格式

输出一个数，代表 $\max_{i=1}^m\{s_i\}$。

6 3
150
-50
1
101
1
100

101

数据规模与约定

对于 $100\%$ 的数据，$1 \le m \le n \le 10^4$，$-10^4 \le a_i \le 10^4$。