题目描述

给定一个非负整数数组 $\textit{nums}$ 和一个整数 $k$，你需要将这个数组分成 $k$ 个非空的连续子数组，使得这 $k$ 个子数组各自和的最大值最小。

返回分割后最小的和的最大值。

子数组是数组中连续的部分。

输入格式

第一行两个正整数 $n, k$，分别表示数组 $\textit{nums}$ 的长度和需要分割成的子数组个数。

第二行 $n$ 个非负整数 $\textit{nums}_1, \textit{nums}_2, \dots, \textit{nums}_n$，表示数组 $\textit{nums}$ 中的元素。

输出格式

输出一行一个整数，表示分割后最小的和的最大值。

样例

样例 1

样例输入 1

5 2
7 2 5 10 8

样例输出 1

18

样例解释 1

一共有四种方法将 $\textit{nums}$ 分割为 $2$ 个子数组。 其中最好的方式是将其分为 $[7,2,5]$ 和 $[10,8]$。 因为此时这两个子数组各自和的最大值为 $18$，在所有情况中最小。

样例 2

样例输入 2

5 2
1 2 3 4 5

样例输出 2

9

样例 3

样例输入 3

3 3
1 4 4

样例输出 3

4

说明/提示

• $1 \le n \le 1000$
• $0 \le \textit{nums}_i \le 10^6$（$1 \le i \le n$）
• $1 \le k \le \min(50, n)$