Farmer John 是惊人的会计高手，意识到经营农场的钱可能会耗尽。他已计算并记录未来 $N$（$1 \le N \le 100,000$）天每天所需的准确支出（$1 \le money_{i} \le 10,000$）。

FJ 要为按顺序排列的恰好 $M$（$1 \le M \le N$）个财务期间制定预算，称它们为“fajomonths”。每个期间包含一个或多个连续的日子，每天恰好属于一个期间。

FJ 希望安排这些期间，使支出最高的期间的支出尽可能小，从而确定月度支出上限。

输入格式

第 1 行：两个空格分隔的整数 $N$ 和 $M$。第 $2\ldots N+1$ 行：第 $i+1$ 行包含 Farmer John 在第 $i$ 天花费的美元数。

输出格式

第 1 行：Farmer John 可以采用的最小月度上限。

样例

输入格式 1

7 5
100
400
300
100
500
101
400

输出格式 1

500

说明

若 Farmer John 将前两天组成一个月，第 3、4 天组成一个月，最后三天各自组成一个月，每月支出至多 500 美元。其他任何安排都需要更大的最小月度上限。

题目来源：USACO 2007 年 3 月。