题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

5 2
7 2 5 10 8

18

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

5 2
1 2 3 4 5

9

3 3
1 4 4

4

数据范围

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