题目描述

在一个神奇的国度里，有一只编程兔，它精通各种编程语言和算法，小花是它的好朋友。

某天小花给编程兔送来了 $n$ 袋萝卜（编号 $1$ 到 $n$），每袋有一定数量的萝卜。编程兔要将这些萝卜分给 $m$ 只小兔子，兔子按编号 $1$ 到 $m$ 依次排队领取，萝卜按袋的编号从小到大顺序发放，所有萝卜必须分完且无剩余。分配规则为：每只兔子只能领取连续的若干袋萝卜，每只兔子至少领取一袋，一袋萝卜只能分给一只兔子，不能拆分。

编程兔希望萝卜分配得尽可能平均，即让得到萝卜数量最多的那只兔子，其萝卜数量尽可能少。请你求出这个最小的最大值。

输入格式

第一行是两个正整数 $n$ 和 $m$，表示萝卜的袋数和兔子的数量。

第二行是 $n$ 个正整数，依次表示每袋萝卜的数量。

输出格式

输出只有一行一个整数，表示得到萝卜最多的那只兔子最少可以得到的萝卜数量。

样例

9 3
1 2 3 4 5 6 7 8 9

17

提示

样例中最优分配方案为：第 $1$-$5$ 袋萝卜分给第一只兔子，总数 $15$ 个；第 $6$-$7$ 袋分给第二只兔子，总数 $13$ 个；第 $8$-$9$ 袋分给第三只兔子，总数 $17$ 个。此时得到萝卜最多的兔子有 $17$ 个，这是所有分配方式中"最大值最小"的结果。

若按 $1$-$4$ 袋（$10$ 个）、$5$-$7$ 袋（$18$ 个）、$8$-$9$ 袋（$17$ 个）分配，最多的兔子有 $18$ 个，并非最优。

数据范围

• $n, m \le 10^5$
• 每袋萝卜的数量 $\le 10^5$