该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

练习册装箱

题目描述

有 $n$ 本练习册排成一排，从左到右编号为 $1,2,\dots,n$。

第 $i$ 本练习册的厚度为 $a_i$。

现在要把这些练习册按原来的顺序装进最多 $k$ 个箱子中。

每个使用的箱子中必须放入连续的至少一本练习册。每本练习册恰好放入一个使用的箱子中，不能遗漏，不能重复，不能拆开，也不能改变练习册的顺序。

如果一个箱子的容量为 $X$，那么每个使用的箱子中练习册的厚度总和都不能超过 $X$。

请你求出最小的箱子容量 $X$，使得所有练习册都能被装完。

输入格式

第一行输入两个整数 $n,k$，表示练习册数量和最多可以使用的箱子数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 本练习册的厚度。

输出格式

输出一个整数，表示最小的箱子容量 $X$。

输入输出样例 #1

输入 #1

5 3
7 2 5 10 8

输出 #1

14

输入输出样例 #2

输入 #2

5 5
4 1 7 2 6

输出 #2

7

说明/提示

对于样例 #1，当箱子容量为 $14$ 时，可以分成：

[7, 2, 5] [10] [8]

三个箱子中的厚度和分别为 $14,10,8$，均不超过 $14$。

如果箱子容量只有 $13$，则至少需要 $4$ 个箱子，所以答案为 $14$。

对于样例 #2，最多可以使用 $5$ 个箱子，因此可以让每本练习册单独装入一个箱子。此时箱子容量至少要能放下最厚的一本练习册，所以答案为 $7$。

数据范围

• $1 \le k \le n \le 10^5$
• $1 \le a_i \le 10^6$

答案可能超过 int 范围，请使用 long long。