配点 : $500$ 点

問題文

高橋君が住む世界の一週間は $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$ の生産量の総和を指します。

制約

• 入力はすべて整数
• $1 \le N \le 5000$
• $1 \le A_i \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

出力

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

7
10 10 1 1 1 1 1

50

例えば曜日 $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$ 以上にすることはできません。

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

5100000000

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

236980