对于给定的一个长度为 N的正整数数列 A[i]，现要将其分成 M(M≤N)段，并要求每段连续，且每段和的最大值最小。

例如，将数列 4  2  4  5  1要分成 3段：

若分为 [4 2][4 5][1]，各段的和分别为 6,9,1 ，和的最大值为 99；

若分为 [4][2 4][5 1]，各段的和分别为 4,6,6，和的最大值为 6；

并且无论如何分段，最大值不会小于 6。

所以可以得到要将数列 4  2  4  5  1要分成 3段，每段和的最大值最小为 6 。

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

第 2行包含 N个空格隔开的非负整数 A[i]，含义如题目所述。

对于 40%的数据，有 N≤1000；

对于 100%的数据，有 N≤10^5，M≤N， A[i]之和不超过 10^9。