小Y有很多作业，每次作业中都有很多题目，小Y会按顺序完成每一道题目。小Y希望用 天完成所有题目，但她不希望自己写题的时候被打断。即，小Y不会把一道正在写的题目留到第二天继续写。

给出每一道题需要花费的时间，求小Y每天写题时间的最大值最小是多少。

【输入格式】 第一行包含两个正整数 n 、 m ，代表小Y的题目数量和用来写作业的天数。

下面一行有 n 个正整数 ，ai代表每道题需要 ai的时间完成。

【输出格式】 输出包含一个整数 ，代表小Y每天写题时间最大值的最小值。

样例

输入
3 2
3 1 2
输出
3

输入
10 3
2 4 1 5 6 3 5 2 4 8
输出
14