题目描述

给定 $n$ 个正整数和一个整数 $k$。请把数组分成 $k$ 个连续子数组，使得"各子数组之和的最大值"尽可能小。求这个最小的最大子数组和。

输入格式

第一行两个整数 $n$、$k$。 第二行 $n$ 个整数 $x_1,\dots,x_n$。

输出格式

一个整数，表示最小的"最大子数组和"。

数据范围

$1\le n\le 2\times10^5$，$1\le k\le n$，$0\le x_i\le 10^9$。

样例

输入：

5 3
2 4 7 3 5

输出：

8

提示：二分"最大子数组和" $x$，贪心分段统计段数是否 $\le k$。改编自 CSES 1085。