题目描述

给定一个包含 $n$ 个正整数的数组，任务是将数组划分为 $k$ 个连续的非空子数组，使得所有子数组的和的最大值尽可能小。请求出这个最小的最大值。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别代表数组的长度和需要划分的子数组个数。
第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$，表示数组的元素。

输出格式

输出一行一个整数，表示子数组和的最大值的最小可能值。

样例

5 3
2 4 7 3 5

8

样例解释
一种最优的划分方式为 $[2, 4]$、$[7]$、$[3, 5]$，三个子数组的和分别为 $6, 7, 8$，最大值为 $8$。可以证明无法使最大值更小。

数据范围

• $1 \le k \le n \le 2 \times 10^5$
• $1 \le x_i \le 10^9$