No submission language available for this problem.

题目描述

关小山的师兄正运营着一个宗门内的小组织，运营组织需要不少灵石来维护组织内的成员，但这灵石的储备捉襟见肘了。他找到关小山，并希望关小山能够帮助自己计算一下应该如何设计灵石的供应比较合适。

关小山盯着师兄提供的支持 N 个任务所需要花费的灵石，他决定设计在连续的 M 个任务周期去创建花费预案。每一个任务周期中包含着一个或连续多个任务。他的目标是安排每个任务周期中的任务数量，令花费灵石最多的那个任务周期的花费尽可能地少。

输入

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

之后的 N 行，每行包含一个整数，表示每个任务需要的灵石花费。

输出

一行一个整数，表示 花费灵石最多那个任务周期的花费 的最小值。

样例

7 4
100
400
300
200
500
201
400

601

Sample 1 说明

• 前两次任务作为一个任务周期：500
• 第三次第四次任务作为一个任务周期：500
• 第五次任务单独做一个任务周期：500
• 最后两次任务作为一个任务周期：601

其它的分配方案的周期最大的最小值，不会比 601 更小了。

数据限制

1 ≤ N ≤ 100000

1 ≤ M ≤ N

1 ≤ 每个任务的灵石花费 ≤ 10000