#2491. Treats for the Cows

Treats for the Cows

题目描述

约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1\red{N(1≤}N\red{N≤}2000)\red{2000)}份美味的零食来卖给奶牛们.

每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:

零食按照1...N\red{1...N}编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每天可以从盒子的任一端取出最外面的一个.

与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.

每份零食的初始价值不一定相同.约翰进货时,第i\red{i}份零食的初始价值为Vi(1\red{V_i(1≤}Vi\red{V_i≤}1000)\red{1000)}

i\red{i}份零食如果在被买进后的第a\red{a}天出售,则它的售价是Vi×a\red{V_i\times a}

Vi\red{V_i}的是从盒子顶端往下的第i\red{i}份零食的初始价值.

约翰告诉了你所有零食的初始价值,并希望你能帮他计算一下,在这些零食全被卖出后,他最多能得到多少钱.

输入格式

1\red{1 }行:单个整数, N\red{N }

2..N+1\red{2..N+1 }行:第 i+1\red{i+1 }行包含处理 V(i)\red{V(i) }的值

输出格式

1\red{1 }行:FJ\red{FJ }通过出售零食可以获得的最大收入

样例

输入样例

5

1

3

1

5

2

输出样例

43

提示

五次款待。第一天,FJ\red{FJ}可以出售treat\red{treat}#1\red{1(}价值1\red{1)}或处理#5\red{5(}2\red{2)}

输出详细信息:

FJ\red{FJ}按以下顺序销售\red{(}1\red{1}3\red{3}1\red{1}5\red{5}2\red{2)}指数:1\red{1}5\red{5}2\red{2}3\red{3}4\red{4,}使1×1+2×2+3×3+4×1+5×5=43\red{1\times 1+2\times 2+3\times 3+4\times 1+5\times 5=43}