時間制限 : sec, メモリ制限 : KB
English / Japanese  

割り当て

重さがそれぞれ $w_i (i = 0, 1, ... n-1)$ の $n$ 個の荷物が、ベルトコンベアから順番に流れてきます。これらの荷物を $k$ 台のトラックに積みます。各トラックには連続する 0 個以上の荷物を積むことができますが、それらの重さの和がトラックの最大積載量 $P$ を超えてはなりません。最大積載量 $P$ はすべてのトラックで共通です。

$n$、$k$、$w_i$ が与えられるので、すべての荷物を積むために必要な最大積載量 $P$ の最小値を求めるプログラムを作成してください。

入力

最初の行に荷物の数 $n$ とトラックの数 $k$ が空白区切りで与えられます。続く $n$ 行に $n$ 個の整数 $w_i$ がそれぞれ1行に与えられます。

出力

$P$ の最小値を1行に出力してください。

制約

  • $1 \leq n \leq 100,000$
  • $1 \leq k \leq 100,000$
  • $1 \leq w_i \leq 10,000$

入力例 1

5 3
8
1
7
3
9

出力例 1

10

1台目のトラックに2つの荷物 $\{8, 1\}$,2台目のトラックに2つの荷物 $\{7, 3\}$、3台目のトラックに1つの荷物 $\{9\}$ を積んで、最大積載量の最小値が 10 となります。


入力例 2

4 2
1
2
2
6

出力例 2

6

1台目のトラックに3つの荷物 $\{1, 2, 2\}$,2台目のトラックに1つの荷物 $\{6\}$ を積んで、最大積載量の最小値が 6 となります。