某班级的班主任要组织一次长跑比赛，为了公平起见，他决定将已经排成一排的 N 位同学，按顺序分成 M 组进行比赛。每组学生的总跑步成绩为该组所有学生的跑步成绩之和。
分组方式为：按照当前排队的顺序，从前向后，选取连续的若干位同学，作为第一组的选手。
第一组选定后，让第一组的同学出列，继续从前向后选取连续的若干位同学，作为第二组的选手。
以此类推，直到将选手分成正好 M 组。
为了让比赛更加的公平，班主任调取了每位同学本年度的跑步比赛成绩的平均分。他希望各组的实力差尽可能的小。因此，他的分组目标是：寻求一个分组方案，使得所 N 位同学按上述规则分成 M 组后，组内选手成绩平均分总和最大的那一组的成绩和，在所有的分组方案中，是最小的。
请你编程，帮助老师计算出，组内选手成绩平均分总和最大值，最小是多少？
第一行包含两个整数 N 和 M，用单个空格隔开。
接下来 N 行，第 i 行读入一个整数 A_i，表示第 i 位学生的年度跑步平均分。
输出一个整数，表示合理分组后，组内选手成绩平均分总和最大组的最小值。
7 5 2 8 6 1 4 9 3
10
10 3 3 5 10 1 20 9 12 18 9 30
39
20 8 10 32 43 112 144 110 30 20 11 131 90 12 87 49 27 48 45 19 98 37
189
假设将前两位学生分为一组 (2+8)，第三、第四位学生分为一组 (6+1)，接下来三位学生分别作为单独的一组 (4), (9), (3) ，这样分数总和最大组的成绩为 10。
其他任何分组方案的最大组成绩都会更大。
对于 20\% 的数据，保证 1 \leq N \leq 20， 1 \le M \le 10。
对于 100\% 的数据，保证 1 \leq N \leq 100000，1 \leq M \leq N，1 \le A_i \le 10000。