题目描述

王老师有一块 1 * 1 * N 的巧克力（每个1 * 1 * 1 的部分有一个营养值Ai），想分给 K 个学生，并且每个学生必须得到一整块，即最终只能分成 K 块，每个学生所得到的营养值即为得到巧克力每部分的营养值之和。
王老师很喜欢淘汰学生，这次他不允许分得营养值最大的那个学生所得的营养值太大，不然他就会把那个学生淘汰。所以，避免学生被淘汰，你必须使分得营养值最大的那个人的营养值尽量小。

输入格式

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

输出格式

一行，分得最多的那个学生的最少的营养值。

样例输入

5 2
2 1 3 4 5

样例输出

9

数据范围

对于30%数据 N <= 30, K <= 10。
对于100%数据 N <= 100000, K <= N, Ai <= 10^9。

限制

1s

样例解释

有如下分法：
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。

来源

CWOI新高二专题测试二