题目描述

小 $Q$ 是一个聪明的中学生, 在学校住宿。他敏锐的意识到自己要破产了, 因为预计的生活费很难坚持到学期末了。他又不想重新跟妈妈要钱, 小 $Q$ 想用学过的知识来解决问题, 所以他计算并记录下了接下来 $N$ 天里每天需要的花费。

小 $Q$ 打算为连续的 $M$ (到期末) 个财政周期创建预算案, 他把一个财政周期重新命名为 $pr$ 月。每个 $pr$ 月包含一天或连续的多天, 每天被恰好包含在一个 $pr$ 月里。

小 $Q$ 的目标是合理安排每个 $pr$ 月包含的天数, 使得花费最多的 $pr$ 月的花费尽可能少。

输入格式

第一行包含两个整数 $N, M$, 用单个空格隔开。

接下来 $N$ 行, 每行包含一个 $1$ 到 $10000$ 之间的整数, 按顺序给出接下来 $N$ 天里每天的花费。

输出格式

一个整数, 即最大月度花费的最小值。

样例1

7 5
100
400
300
100
500
101
400

500

样例1解释说明

观察样例数据，如果小 $Q$ 将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大 $pr$ 月花费为 $500$。其他任何分配方案都会比这个值更大。

数据范围

保证所有的数据均满足，$1\leq N\leq 10^5,1\leq M\leq N$