题目描述

Farmer John 是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N 天里每天需要的开销。

Farmer John 打算把这 N 天的开销划分成连续的 M (1 ≤ M ≤ N) 个财政周期，每一个财政周期命名为 fajo 月。每个 fajo 月包含一天或连续的多天，每天被恰好包含在一个 fajo 月里。

Farmer John 的目标是合理安排每个 fajo 月包含的天数，使得开销最多的 fajo 月的开销尽可能少。

输入格式

第一行，两个整数 N 和 M ( 1 ≤ M <= N ≤ 100,000 )

接下来 N 行，每行一下整数，表示第 i 天的开支 （ 1 <= 每天开支 <= 10000 ）。

输出格式

一个整数，表示预算的 M 份预算的最大值的最小值

样例

7 5
100
400
300
100
500
101
400

500

样例解释

第 1 、 2 天做一份预算，第 3 、 4 天做一份预算，第 5 天一份，第 6 天一份，第 7 天一份，那么各份预算最大的是 500 。其他划分方法都不能比这个更少。