Description

现在有一块1*1*N 的巧克力（每个1*1*1 的部分有一个营养值Ai），想分给K 个小朋友，并且每个小朋友必须得到一整块，即最终只能分成K 块，每个小朋友所得到的营养值即为得到巧克力每部分的营养值之和。
这几个小朋友的自尊心很强，尤其是不允许分得营养值最大的那个人所得的营养值太大。所以，为了照顾好他们，你必须使分得营养值最大的那个人的营养值尽量小。

Input

第1 行：两个整数N 和K
第2 行：N 个整数Ai，相邻整数用空格隔开

Output

一行，分得最多的那个人的最少巧克力

Sample Input

5 2
2 1 3 4 5

Sample Output

9

Hint

样例解释：有如下分法
2 | 1 3 4 5 -> 2 和 13 -> max=13
2 1 | 3 4 5 -> 3 和 12 -> max=12
2 1 3 | 4 5 -> 6 和 9 -> max=9
2 1 3 4 | 5 -> 10 和 5 -> max=10
再对所有取最小 min=9

对于30%数据 N <= 30, K <= 10
对于100%数据 N <= 100000, K <= N, Ai <= 1e9