102854: [AtCoder]ABC285 E - Work or Rest

Problem Statement

In the world where Takahashi lives, a week has $N$ days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the $i$-th day of week is defined by a sequence $A$ of length $N$ as follows:

• if the $i$-th day of week is "holiday", its productivity is $0$;
• if the $i$-th day of week is "weekday", its productivity is $A_{\min(x,y)}$, if the last holiday is $x$ days before and the next one is $y$ days after.
  • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the $1$-st, $2$-nd, $\dots$, and $N$-th day of week.

Constraints

• All values in the input are integers.
• $1 \le N \le 5000$
• $1 \le A_i \le 10^9$

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the $2$-nd and $4$-th day of week and "weekday" to the rest to achieve a productivity of $50$ per week:

• the $1$-st day of week ... $x=4$ and $y=1$, so its productivity is $A_1 = 10$.
• the $2$-nd day of week ... it is holiday, so its productivity is $0$.
• the $3$-st day of week ... $x=1$ and $y=1$, so its productivity is $A_1 = 10$.
• the $4$-th day of week ... it is holiday, so its productivity is $0$.
• the $5$-th day of week ... $x=1$ and $y=4$, so its productivity is $A_1 = 10$.
• the $6$-th day of week ... $x=2$ and $y=3$, so its productivity is $A_2 = 10$.
• the $7$-th day of week ... $x=3$ and $y=2$, so its productivity is $A_2 = 10$.

It is impossible to make the productivity per week $51$ or greater.

Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

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

Sample Output 3

236980

问题描述

在Takahashi居住的世界中，一周有$N$天。

Takahashi是AtCoder王国的国王，他将“工作日”或“假日”分配给每周的每一天。分配应该是所有周相同的。至少有一天应该被分配为“假日”。

在这样的条件下，第$i$天的工作效率定义为长度为$N$的序列$A$，如下所示：

• 如果第$i$天是“假日”，那么其工作效率为$0$；
• 如果第$i$天是“工作日”，那么其工作效率为$A_{\min(x,y)}$，如果上一个假日是在$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$

输出

将答案作为整数打印。

样例输入 1

7
10 10 1 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$或更高。

样例输入 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

样例输出 2

5100000000

样例输入 3

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

样例输出 3

236980