该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

WEI昨天大发神威直接一举拿下第一（哼，原来在座的各位都是垃圾），WEI今天还在学大家都没学到的东西，那就是前缀和！不过他在想很深奥的事情，前缀和中把sum[i]当成a[0]-a[i]的和来算，那如果，把a数组分成很多段，会怎么样呢？
例如现在有一个数列a为：4 2 4 5 1，WEI想把他分成三份，如果分成了[4,2],[4,5],[1],则各段的和分别为6，9，1。如果分成了[4],[2,4],[5,1],则各段的和分别为4，6，6。然后WEI发现了很神奇的一件事！无论如何去分段，最大值都不会小于6，也就是说每段和的最大值最小为6！于是WEI现在来了兴趣，他想知道一个长度为N的数列，现在如果分成M段，要求每段连续，那么此时每段和的最大值最小为多少？

Description

Given two integers x and y, print the sum.

Format

Input

第 1 行包含两个正整数 N，M；

第 2 行包含 N 个空格隔开的非负整数，含义如题面所述。 对于 所有数据，$N \leq 10^5$，$M \leq N$， 数列中所有数均在int范围内

Output

仅包含一个正整数，即每段和最大值最小为多少。

Samples

5 3
4 2 4 5 1

6

Limitation

1s, 1024KiB for each test case.