ID: L43203

传统题

2000ms

128MiB

普及

上传者:

标签>

M4

M4第二学期

M4-第32课

函数最值与优化

不用全部试也能找到最优答案吗

最值与变化模型

优化算法

算法相关

算法-二分答案

算法-单调判定

算法-贪心分段

课堂题

最轻松的训练计划

题目描述

正整数任务按原顺序划分为不超过k个非空连续段，最小化最大段和。

输入格式

第一行n、k；第二行n个正整数a_i，保证1≤k≤n且总和在64位范围。

输出格式

输出最小可能最大段和。

数据范围

$1 \le k \le n \le 2\times 10^5$ ；
$1 \le a_i \le 10^9$ 。

样例

输入

5 2
7 2 5 10 8

输出