0991 - Takenoko Truck Transport

ストーリー

ei1821は筍派(急進派)である。

ei1821は自分の夢を叶えるべくとある工場を建造した。
それは、超巨大筍を大量生産することである。
なんやかんやでその夢は実現しラインも完成した。ei1821は心優しいためこの超巨大筍を他の人にも金を払えば無料でで恵んでやろうと考えた。しかし、とある問題が浮上する。
ei1821の心が広すぎたせいか、生産される筍の大きさにムラができたのだ。
だから、トラックごとに載せる量が変わってしまうことがあるのだ。
それだけなら超巨大トラックを1つだけ用意してまとめて載せたものだが、もう一つの問題によりそれは叶わない。
この筍が如何せん重すぎたのだ。なんと重量の単位がエクサなのである。
さすがに1個何エクサグラムの筍を何万個と載せられるトラックは発注が難しいので困ったものだ。
それでも重すぎて特注品を用意するしかない。
それなら1台も100台も手間自体は変わらない（謎理論)。

本題

重量がそれぞれw_iエクサグラムの筍がn個、ベルトコンベアから順番に流れてくる。これらをk台のトラックに積むが、発注の金額の問題で最大積載量はできるだけ抑えたい。なので、各トラックに積む筍の重さの和はすべてP以下にする。
特注はまとめてするため、k台のトラックの最大積載量は等しい。

入力

1行目に、筍の個数nとトラックの台数kが与えられる。
続くn行に、それぞれの筍の重量w_iが与えられる。

出力

最小の最大積載量Pを出力する。

最後の改行を忘れずに。

制約

• $1$ ≤ $n$, $k$ ≤ $100,000$
• $1$ ≤ $w$_$i$ ≤ $10,000$
• 各トラックには連続する0個以上の荷物を積むことができる

入出力例

例1

入力

5 3
8
1
7
3
9

出力

10

1台目に2つの筍{8,1}、2台目に2つの筍{7,3}、3台目に1つの筍{9}を積むと最大積載量は10になり、これが最小である。

例2

入力

10 7
15
11
31
19
33
46
50
12
35
3

出力

50

補足

なお、この問題は螺旋本を参考にしました。なので螺旋本を参考にACするのは正しい判断です。
理解さえすれば勝ち。