对于给定的一个长度为 NNN 的正整数数列 AAA ，现要将其分成 MMM 段，并要求每段连续，且每段和的最大值最小。

例如，将数列 4  2  4  5  14 \ \ 2 \ \ 4 \ \ 5 \ \ 14 2 4 5 1 要分成 333 段：

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

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

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

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

第 111 行包含两个正整数 NNN，MMM；

第 222 行包含 NNN 个空格隔开的非负整数 AiA_iAi，含义如题目所述。

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

对于 20%20\%20%的数据，有 N≤10N \leq 10N≤10；

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

对于 100%100\%100%的数据，有 N≤105N \leq 10^5N≤105，M≤NM \leq NM≤N， AiA_iAi 之和不超过 10910^9109 。