家具运输

时间限制: 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$ 。

6 2
3 2 4 4 4 7

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

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

对于所有数据， $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$ 。