問題
もけちゃんは今からプログラミングコンテストに参加しようと思っている。
このプログラミングコンテストでは問題が $N$ 問出題される。
もけちゃんが問題 $i \ (1 \leq i \leq N)$ を解くのに要する時間は $t_i$ である。
良い成績を残したいもけちゃんは、$K$ 匹に分身することにした。
分身することで、それぞれのもけちゃんが並行して問題を解くことができる。
ここで、分身後のそれぞれのもけちゃんについて次のことが分かっている。
- 一旦任意の問題に取り掛かると、その問題を解き終わるまでは中断できない。
- 複数匹で $1$ つの問題を解くことはできない。
- 問題が解けたら、すぐに次の問題に取り掛かる。
- 問題が解き終わって次の問題に取り掛かる際にかかる時間はゼロである。
もけちゃんはできる限り最短ですべての問題を解き終わりたいと思っている。
それぞれのもけちゃんに適切に問題を分配し、すべての問題を解き終わる時間を最小化しなさい。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $K$ $t_1$ $t_2$ $\vdots$ $t_N$
出力
すべての問題を解き終わるのに要する時間の最小値を $1$ 行で出力せよ。 出力の末尾に改行を入れること。
制約
- $1 \leq N \leq 10$
- $2 \leq K \leq 5$
- $1 \leq t_i \leq 10^7 \ (1 \leq i \leq N)$
入出力例
入力例１
4 2 5 8 7 11
出力例１
16
$2$ 匹のもけちゃんが問題を解く。一方が問題 $1, 4$ を、もう一方が問題 $2, 3$ を担当するのが最適である。
入力例２
4 4 5 10 25 40
出力例２
40
$4$ 匹のもけちゃんそれぞれが $1$ 問ずつ担当すればよく、これが最適である。
入力例３
2 3 1933 1727
出力例３
1933
$1$ 匹は $1933$ の間、何も行わない。
入力例４
10 4 364 815 77 950 249 688 102 551 224 878
出力例４
1242