ストーリー

やきとりくんは、できあがったパンの生地をオーブンで焼き上げることにしました。
パンパーティーを開く時間を調整するために、パンの生地を全て焼き上げるまでにどのくらい時間がかかるのかを計算しようとしています。

問題文

やきとりくんは、$N$ 個のパンの生地を焼き上げようとしています。
$i \: (1 \leq i \leq N)$ 個目のパンの生地は、オーブンを連続した $T_i$ 分間使うことで焼き上げることができます。
$1$ つのオーブンを $2$ つ以上のパンの生地のために同時に使うことはできません。

$K$ 個のオーブンを使えるとき、$N$ 個のパンの生地を全て焼き終わるまでに最短で何分かかるでしょうか。 なお、オーブンを使う時間以外は無視できるものとします。

制約

• $1 \leq K \leq N \leq 8$
• $1 \leq T_{i} \leq 10^{9} \: (1 \leq i \leq N)$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K
T1 T2 ...... TN

出力

問題の答えを一行に出力せよ。

入出力例

5 2
1 3 4 6 8

11

$1$ つ目のオーブンでは $1、3、4$ 番目のパンの生地、 $2$ つ目のオーブンでは $2、5$ 番目のパンの生地を焼き上げることにすると、$11$ 分で全てのパンの生地を焼き上げることができます。

8 8
100 200 300 400 500 600 700 800

800

パンの生地とオーブンの個数が等しいため、同時に全てのパンの生地を焼き上げることができます。