题目描述

有 $n$ 个任务按固定顺序排列，第 $i$ 个任务工作量为 $a_i$。现在要将它们划分为恰好 $m$ 个非空的连续批次，每个任务属于且仅属于一个批次，任务顺序不能改变。

一个方案的最大批次工作量，是各批次工作量之和的最大值。请让这个值尽可能小。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出最小可能的最大批次工作量。

样例

5 2
7 2 5 10 8

18

数据规模与约定

• $1\le m\le n\le2\times10^5$；
• $1\le a_i\le10^9$。

答案与工作量总和可能超过 int 范围，必须使用 long long。