#BT01. 切片上限

切片上限

切片上限

传送带上依次摆着 nn 箱货物,第 ii 箱的重量为 aia_i。你要在箱子之间放置隔板,将它们分成恰好 kk 段非空连续区间。

一段的载荷为其中所有箱子的重量之和。请使所有段中的最大载荷尽可能小,并输出这个最小值。重量可以为零。

输入格式

第一行包含两个整数 n,kn,k。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一个整数,表示最大段载荷的最小可能值。

样例 1

5 3
4 2 4 5 1
6

一种划分为 [4],[2,4],[5,1][4],[2,4],[5,1],三段载荷分别为 4,6,64,6,6。

样例 2

4 3
0 5 0 5
5

一种划分为 [0],[5,0],[5][0],[5,0],[5]。

数据范围

  • 1≤k≤n≤200 0001\le k\le n\le 200\,000。
  • 0≤ai≤1090\le a_i\le 10^9。