3449. [USACO Feb06]特殊津贴

【题目背景】

众所周知，$FJ$是个一毛不拔的铁公鸡

但有时，他心情很好，看到奶牛产的奶很多，就会大发慈悲地给高产奶牛发一点零花钱

奶牛们发现了这个秘密，开始想尽办法（比如膜拜神犇，学习奶牛魔法什么的），提高产奶量，从$FJ$手中赚取零花钱.......

【题目描述】

于是很快奶牛们拥有了大笔不知该怎么花的钱．为此，$FJ$购置了$N(1≤N≤2000)$份美味的零食来卖给奶牛们，每天售出一份零食．当然他希望这些零食全部售出后能得到最大的收益．这些零食有以下这些有趣的特性：

•零食按照$1$..$N$编号，它们被排成一列放在一个很长的盒子里．盒子的两端都有开口，$Farmer$ $John$每天可以从盒子的任一端取出最外面的一个．（就不能一个一个拿出来再放回去吗）

•与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃．当然，这样$FJ$就可以把它们卖出更高的价钱．

•每份零食的初始价值不一定相同．约翰进货时，第$i$份零食的初始价值为$V_i$($1≤V_i≤1000)$．

•第$i$份零食如果在被买进后的第$a$天出售，则它的售价是$v_i×a$．

$V_i$的是从盒子顶端往下的第$i$份零食的初始价值．$Farmer$ $John$告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱．

【输入格式】

第1行:一个整数 $N$

下面的第$2$行到第$N+1$行:每行一个数$V_i$,表示第$i$个零食的价值

【输出格式】

只有一行，表示$Farmer$ $John$能得到的最大的收益

【样例输入】

5
1
3
1
5
2

【样例输出】

43

【样例解释】

$5$个零食，第一天$FJ$可以售出第$1$个零食（价值$1$）或者第$5$个零食（价值$2$）

按照$1,5,2,3,4$的顺序售出，可以得到$1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43$的收益。

【提示】

注意内存

【来源】

$洛谷P2858$,$[USACO06FEB]Treats$ $for$ $the$ $Cows$ $G/S$