该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

蓄力与收割

题目描述

你正在游玩一款动作游戏，面前有 $n$ 只怪物排成一排，依次编号为 $1$ 到 $n$。第 $i$ 只怪物提供的基础经验值为 $a_i$（注意 $a_i$ 可能为负数）。

你初始的经验值为 0，初始的“蓄力倍率”为 1。你必须按照 $1$ 到 $n$ 的顺序依次面对每一只怪物，并在面对时做出以下两种选择之一：

• 收割（攻击）：你击杀该怪物，获得 $a_i \times M$ 的经验值，其中 $M$ 为当前的蓄力倍率。击杀完成后，倍率 $M$ 保持不变。
• 蓄力（跳过）：你不攻击该怪物，放弃它的经验值。但你的蓄力倍率 $M$ 会增加 1。

请计算在面对完所有 $n$ 只怪物后，你能够获得的最大总经验值。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 3000$)，表示怪物的数量。

第二行包含 $n$ 个整数，依次表示 $a_1, a_2, \dots, a_n$ ($-10^5 \le a_i \le 10^5$)。

输出格式

输出一行一个整数，表示你能够获得的最大总经验值。

输入输出样例 #1

输入 #1

3
10 10 10

输出 #1

40

输入输出样例 #2

输入 #2

5
-5 4 -2 8 1

输出 #2

36

说明/提示

样例 1

放弃第 1 只怪物，倍率变为 2。

攻击第 2 只怪物，获得 $10 \times 2 = 20$ 经验，倍率仍为 2。

攻击第 3 只怪物，获得 $10 \times 2 = 20$ 经验。

总经验值为 $20 + 20 = 40$。

样例 2

最佳策略是放弃第 1、2、3 只怪物，此时连续蓄力 3 次，倍率变为 4。

攻击第 4 只怪物，获得 $8 \times 4 = 32$ 经验。

攻击第 5 只怪物，获得 $1 \times 4 = 4$ 经验。

总经验值为 $32 + 4 = 36$。