Background

dyy第一次来到东北，真是太新奇了！在某天集训结束的晚上发现冬天的超市也卖雪糕，觉得很新奇，于是买了一大袋雪糕。

啊呀，哥们这就是实力，最幸福的一集！——dyy

Description

我们一起数了一下，这一袋雪糕有 $n$ 个，因为一天肯定是吃不完的，所以他计划 $m$ 天吃完这些雪糕。

为了不让雪糕提前融化，他把这些雪糕放进冰箱里，但由于冰箱尺寸较小，因此所有雪糕都被叠放放置，因此想要吃到下面的雪糕，就必须先吃完其上所有叠放的雪糕。

对于每根雪糕，其都有一个寒冷值 $x_i$ 。若寒冷值太高，则吃后则会坏肚子。若dyy每天吃 $b$ 根雪糕，则每天的寒冷值$X_j$为当天吃的雪糕的寒冷值$x_i$的总和：$X=\sum\limits_{i=1}^{b} x_i$。

但由于dyy又菜又爱吃，又不想让自己坏肚子，因此他找到你求助。请你计算一下，在他的计划中，这 $m$ 天里最大的寒冷值最小是多少：$\texttt{max}[X_1,X_2,\cdots,X_m]$。

Format

Input

第一行包含两个整数 $n(1 \le n \le 10^5)$ 和 $m(1 \le m \le n)$ ，表示雪糕数量和吃雪糕的天数。

接下来一行有 $n$ 个空格隔开的非负整数 $a_i(1 \le a_i \le 10^4)$，表示每个雪糕的寒冷值，并且输入顺序为吃雪糕的顺序。

Output

一个正整数，表示这 $m$ 天里最大寒冷值的最小值。

Samples

5 3
4 2 4 5 1

6

Hint

要在三天内吃完五个雪糕，若第一天吃两个，第二天吃两个，第三天吃一个，则会有：

[4 2][4 5][1]

第一天的寒冷值为6，第二天的寒冷值为9，第三天的寒冷值为1。

若第一天吃一个，第二天吃两个，第三天吃两个，则会有:

[4][2 4][5 1]

第一天寒冷值为4，第二天寒冷值为6，第三天寒冷值为6

且其他方法都不会小于6