Description

给出一个长度为 N 的正整数数组 A，不改变数组元素的顺序，将这 N 个数分成 K 组（连续的数字分到一组）。设各组元素的和分别为 S1 , S2 ...... SK ,如何分组使得 S1 ~ SK 中的最大值最小？

Input

第1行：2个数 N ，K。N为数组长度，K 为要分成多少组。

第2行：N个数表示数组元素

Output

输出S1 ~ SK 的最大值，使得它是所有方案中最小的。

Sample Input

6 3
1 2 3 4 5 6

Sample Output

9

Limitation

1s, 1024KiB for each test case.

Hint

2 ≤ K < N ≤ 50000
1 ≤ A[i] ≤ 10^9