問題
とある年中無休の店の店長であるYさんは、今後の繁忙期のうちの $T$ 時間のシフトスケジュール作成に取り掛かっている。この店の店員は $N$ 人であり、各店員のシフトは1時間単位で決めなければならず、 $i$ 番目の店員は $i-1$ 番目の店員の直後にのみ($1 < i \leq N$)、 $j$ 番目の店員は $j+1$ 番目の店員の直前にのみ($1 \leq j < N$)シフトを入れなければならない。
ここで、スケジュールの始まりを $0$ 時として、$k-1$ 時から $k$ 時までの仕事の数を $w_k$ とする($1 \leq k \leq T$)。 $N$ 人のシフトを決めた際に最も多くの仕事をこなすことになる店員について、仕事の数の最小値を求めよ。(説明が分かりにくい場合は入出力例の下の補足を読むこと。)
入力
入力は以下の形式で標準入力から与えられる。
$T$ $N$ $w_1$ $w_2$ ... $w_T$
1行目に時間 $T$ 、店員の数 $N$ が半角スペース区切りで与えられる。 2行目に各時間帯における仕事の数$w_i (1 \leq i \leq T)$が半角スペース区切りで与えられる。
出力
適切にシフトスケジュールを組んだ際、最も多くの仕事をこなすことになる店員について、仕事の数の最小値を出力せよ。出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N < T \leq 10^{5} $
- $1 \leq w_i \leq 10^9 (1 \leq i \leq T)$
入出力例
入力例1
3 2 1 2 3
出力例1
3
店員1が2時間、店員2が1時間の順で働くと、どちらも仕事の数は3となる。これよりも仕事の数を減らすことは出来ないため、最小値は3となる。
入力例2
6 3 7 1 2 3 3 3
出力例2
7
例えば、店員1が1時間、店員2が3時間、店員3が2時間の順で働くと、それぞれ仕事の数は7、6、6となる。このとき最も多くの仕事をこなすことになる店員は店員1であり、その仕事の数は7である。これよりも仕事の数を減らすことは出来ないため、最小値は7となる。
入力例3
3 1 100 100 100
出力例3
300
店員1が一人で全部の仕事を行う必要がある。
補足
数学的に問題文をまとめるなら、こんな感じ。数列 ${w_i}$($1 \leq i \leq T$) について、狭義単調増加な数列 $a_j$($1 \leq j \leq N$,$a_{j-1}< a_j$,$a_0=0,a_N = T$)を定める。このとき、$\displaystyle \sum_{i=a_{j-1}+1}^{a_j}w_i$ の値が最大となるときの $j$ を$ j = M $として、$\displaystyle \sum_{i=a_{M-1}+1}^{a_M}w_i$の最小値をを求めよ。