[Usaco2006 Feb]Treats for the Cows

约翰经常给产奶量高的奶牛发放特殊津贴，因此奶牛们很快便积攒了大量金钱。为了让奶牛们消费，约翰购置了 $N$ 份美味的零食，并计划每天出售一份。他希望在卖完所有零食后获得尽可能多的收益。

这些零食具有如下特点：

• 零食按照 $1$ 到 $N$ 编号，并按编号顺序排成一列，存放在一个两端开口的长盒子中。每天，约翰只能从盒子的任意一端取出最外侧的一份零食出售。
• 与美酒和奶酪类似，零食存放得越久，售价就越高。
• 每份零食的初始价值不一定相同。第 $i$ 份零食的初始价值为 $v_i$。
• 如果第 $i$ 份零食在第 $a$ 天出售，其售价为 $v_i\times a$。

第一份零食在第 $1$ 天出售，此时 $a=1$。此后每天将 $a$ 增加 $1$。

给定盒子中所有零食按顺序排列的初始价值，请计算约翰通过合理安排出售顺序所能获得的最大总收益。

输入格式

第一行包含一个整数 $N$，表示零食的数量。

接下来 $N$ 行，第 $i$ 行包含一个整数 $v_i$，表示第 $i$ 份零食的初始价值。

输出格式

输出一个整数，表示约翰卖完所有零食后能够获得的最大总收益。

样例输入

5
1
3
1
5
2

样例输出

43

数据范围

• $1\le N\le 2000$；
• $1\le v_i\le 1000$。

来源与许可

本题为 USACO 2006 February 试题「Treats for the Cows」，题面与测试数据整理自 BZOJ。

样例 1

输入

5
1
3
1
5
2

输出

43