题目描述

小 Atom 有 $N$ 个玩具，她将这些玩具按顺序排列。第 $i$ 个玩具的价值为 $A_i$，她想将这些玩具按顺序放入 $M$ 个盒子中。你可以决定如何划分这些玩具进入盒子，但要求每个盒子内的玩具编号必须连续。定义每个盒子的价值为其中所有玩具的价值和。

小 Atom 希望知道，在所有可能的分法中，最小的盒子价值最大可以是多少。

换句话说，划分玩具到 $M$ 个盒子中后，最小的盒子价值应尽可能大。请你帮她计算这个值。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示玩具的数量和盒子的数量。

第二行包含 $N$ 个非负整数 $A_1, A_2, \dots, A_N$，表示每个玩具的价值。

输出格式

输出一个整数，表示所有可能分法中，最小的盒子价值的最大值。

5 2
1 2 3 4 5

6

提示

解释

• 将玩具划分为两个盒子：可以是 [1, 2, 3] 和 [4, 5]。这时最小盒子的价值是 6，最大最小盒子价值为 6。
• 如果划分为 [1, 2] 和 [3, 4, 5]，最小盒子价值为 3。
• 最优解是让最小的盒子价值为 6。

$1 \leq N \leq 10^5$，$M \leq N$。 $0 \leq A_i \leq 10^8$。