AT_awc0005_d 配達ルートの分割

高橋君は運送会社で配達計画を担当しています。 今日は $ N $ 個の荷物を $ K $ 台のトラックで配達する計画を立てる必要があります。 各荷物には $ 1 $ から $ N $ までの番号が付けられており、荷物 $ i $ の重さは $ A_i $ です。 配達の効率化のため、荷物 $ 1, 2, \ldots, N $ をこの順に並べた列を、それぞれ $ 1 $ 個以上の荷物からなる $ K $ 個の連続区間に分割し、各区間の荷物をそれぞれ $ 1 $ 台のトラックに割り当てることにしました。すべての荷物はちょうど $ 1 $ つの区間に属し、 $ K $ 個の区間と $ K $ 台のトラックは $ 1 $ 対 $ 1 $ に対応します。 各トラックについて、そのトラックに割り当てられた荷物の重さの合計を、そのトラックの **負担量** と呼ぶことにします。 高橋君は、 $ K $ 台のトラックの負担量のうち最も小さい値をできるだけ大きくしたいと考えています。 すべての分割方法を考えたとき、「 $ K $ 台のトラックの負担量の最小値」として達成可能な最大値を求めてください。

> $ N $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ - $ 1 $ 行目には、荷物の個数を表す整数 $ N $ と、トラックの台数を表す整数 $ K $ が、スペース区切りで与えられる。 - $ 2 $ 行目には、各荷物の重さを表す $ N $ 個の整数 $ A_1, A_2, \ldots, A_N $ が、スペース区切りで与えられる。

最適な分割を行ったときの、 $ K $ 台のトラックの負担量の最小値として達成可能な最大値を $ 1 $ 行で出力してください。

### Constraints - $ 1 \leq K \leq N \leq 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - 入力はすべて整数