重さがそれぞれ $w_i (i = 0, 1, ... n-1)$ の $n$ 個の荷物が、ベルトコンベアから順番に流れてきます。これらの荷物を $k$ 台のトラックに積みます。各トラックには連続する 0 個以上の荷物を積むことができますが、それらの重さの和がトラックの最大積載量 $P$ を超えてはなりません。最大積載量 $P$ はすべてのトラックで共通です。
$n$、$k$、$w_i$ が与えられるので、すべての荷物を積むために必要な最大積載量 $P$ の最小値を求めるプログラムを作成してください。
最初の行に荷物の数 $n$ とトラックの数 $k$ が空白区切りで与えられます。続く $n$ 行に $n$ 個の整数 $w_i$ がそれぞれ１行に与えられます。
$P$ の最小値を１行に出力してください。
5 3 8 1 7 3 9
10
１台目のトラックに２つの荷物 $\{8, 1\}$,２台目のトラックに２つの荷物 $\{7, 3\}$、３台目のトラックに１つの荷物 $\{9\}$ を積んで、最大積載量の最小値が 10 となります。
4 2 1 2 2 6
6
１台目のトラックに３つの荷物 $\{1, 2, 2\}$,２台目のトラックに１つの荷物 $\{6\}$ を積んで、最大積載量の最小値が 6 となります。