AT_abc285_e [ABC285E] Work or Rest

[problemUrl]: https://atcoder.jp/contests/abc285/tasks/abc285_e 高橋君が住む世界の一週間は $ N $ 日からなります。 一週間は曜日 $ 1,2,\dots,N $ と進んでいき、曜日 $ N $ が終わると次の週の曜日 $ 1 $ が始まります。 ABC 国の国王である高橋君は、各曜日に「平日」「休日」のどちらかを割り当てます。この割り当ては毎週同じでなければなりません。また、少なくとも $ 1 $ つの曜日を「休日」に割り当てなければなりません。 この条件の下で、曜日 $ i $ の生産量は長さ $ N $ の数列 $ A $ を用いて以下のように定義されます。 - 曜日 $ i $ が「休日」である場合は $ 0 $ - 曜日 $ i $ が「平日」のとき、直前の休日が $ x $ 日前、直後の休日が $ y $ 日後である場合は $ A_{\min(x,y)} $ - 割り当ては毎週繰り返されるため、 直前 / 直後 の「休日」が当日とは別の週に属する可能性があることに注意してください。詳しくはサンプルを参照してください。 上手く割り当てを決めたときの一週間当たりの生産量の最大値を答えてください。 但し、一週間当たりの生産量とは曜日 $ 1,2,\dots,N $ の生産量の総和を指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを整数として出力せよ。

### 制約 - 入力はすべて整数 - $ 1\ \le\ N\ \le\ 5000 $ - $ 1\ \le\ A_i\ \le\ 10^9 $ ### Sample Explanation 1 例えば曜日 $ 2,4 $ を「休日」、残りを「平日」に割り当てることで、以下のように一週間当たりの生産量 $ 50 $ を達成できます。 - 曜日 $ 1 $ ... $ x=4,y=1 $ なので、この曜日の生産量は $ A_1\ =\ 10 $ である。 - 曜日 $ 2 $ ... 「休日」であるので、この曜日の生産量は $ 0 $ である。 - 曜日 $ 3 $ ... $ x=1,y=1 $ なので、この曜日の生産量は $ A_1\ =\ 10 $ である。 - 曜日 $ 4 $ ... 「休日」であるので、この曜日の生産量は $ 0 $ である。 - 曜日 $ 5 $ ... $ x=1,y=4 $ なので、この曜日の生産量は $ A_1\ =\ 10 $ である。 - 曜日 $ 6 $ ... $ x=2,y=3 $ なので、この曜日の生産量は $ A_2\ =\ 10 $ である。 - 曜日 $ 7 $ ... $ x=3,y=2 $ なので、この曜日の生産量は $ A_2\ =\ 10 $ である。 一週間当たりの生産量を $ 51 $ 以上にすることはできません。