给定一个由 $$$n$$$ 整数组成的数组。你必须执行 $$$n$$$ 回合。
最初您的分数是 $$$0$$$。
在第 $$$i$$$ 回合中,您可以保持数组不变,也可以交换数组中任意一对 $$$2$$$ 相邻元素,并在交换后将其中一个恰好更改为 $$$0$$$(并保持其他元素的值不变)。无论哪种情况(无论您是否交换),此后您都将 $$$a_i$$$ 添加到您的分数中。
您可以获得的最高分数是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
输出
打印一个整数——可能的最大分数。
示例
输入 #1
2 3 1
输出 #1
6
输入 #2
5 7 3 9 6 12
输出 #2
52
注意
在第一个示例中,为了获得最高分数,我们执行以下操作。第一回合不做任何事情,将 $$$3$$$ 添加到分数中。交换第一个和第二个元素,并在第二回合将 $$$1$$$ 变为 $$$0$$$,并将 $$$3$$$ 添加到分数中。最终得分为$$$6$$$。