T1 家具运输

题目信息

时间限制: 1s

空间限制: 512M

输入文件: trans.in

输出文件: trans.out

题目描述

有 $n$ 件家具，第 $i$ 件家具的重量为 $a_i$。现在小明要租一台货车运输这些家具，假设货车的载重量为 $w$。

小明运输的方法为：每一轮，小明会反复选择尽量重的家具搬上车，直到车的载重量不能再装为止。（也就是说，从空车开始，不断选择还没有运输过的家具中，搬上车后不会使车上家具总重量大于 $w$ 的家具中最重的一件搬上车）然后他开车把所有车上的家具运到目的地并卸载，之后返回运下一趟。

现在小明想用不超过 $k$ 趟运完所有家具，求车最小可能的载重量 $w$。

输入格式

第一行两个正整数 $n,k$。

接下来一行 $n$ 个用空格分隔的正整数 $a_1,a_2,\dots ,a_n$。

输出格式

输出一行一个正整数，最小可能的 $w$。

样例

样例输入 1

6 2
3 2 4 4 4 7

样例输出 1

13

样例解释 1

因为总重量为 $24$，所以 $2$ 趟运完说明载重量至少 $12$。载重量 $12$ 时，由于装车方法，第一趟只能运 $7+4$，第二趟只能运 $4+4+3$，无法运完。载重量 $13$ 时，第一趟可运 $7+4+2$，第二趟运 $4+4+3$ 即运完。所以载重量最少需要 $13$。

样例输入 2

19 4
2 5 1 12 11 11 15 8 17 19 13 11 3 11 18 13 20 13 3

样例输出 2

52

数据范围与提示

对于所有数据，$1\le n, k, a_i\le 2000$。

对于 $20\%$ 的数据，$n, k, a_i\le 20$。

对于另外 $20\%$ 的数据，$n, k, a_i\le 100$。

对于另外 $20\%$ 的数据，$n, k, a_i\le 500$。