AT_cpsco2019_s2_b.Telephone Q

在夜间电视节目「こんばんはゴジラです」中，进行着如下的翻板游戏。

作为游戏参与者的你，初始时拥有 $0$ 日元。

每块面板上都写有一个符号和一个非负整数，第 $i$ 块面板上写的符号和非负整数分别为 $c_i$、$a_i$。

当你翻开第 $i$ 块面板时，你的所持金额会按照以下规则发生变化：

• 当 $c_i=+$ 时：所持金额增加 $a_i$ 日元。
• 当 $c_i=-$ 时：所持金额减少 $a_i$ 日元。
• 当 $c_i=*$ 时：所持金额变为原来的 $a_i$ 倍。

你可以从 $N$ 块面板中任选 $0$ 块或多块，以任意顺序逐一翻开，并且可以在任意时刻结束游戏。此外，游戏过程中及结束时你的所持金额可以为负数。

你事先知道每块面板上的内容，想要让游戏结束时的所持金额最大化。请输出游戏结束时所持金额的最大值 $M$。

输入以如下格式从标准输入读入。

$N$ $c_1$ $a_1$ $c_2$ $a_2$ $\ldots$ $c_N$ $a_N$

请输出游戏结束时所持金额的最大值 $M$。

限制条件

• $1 \leq N \leq 1000$
• $0 \leq a_i \leq 1000$
• $c_i$ 为 +、-、* 之一。
• 游戏结束时的所持金额最大值 $M$ 不超过 $10^9$。

样例解释 1

依次翻开「$+100$」、「$+300$」、「$*3$」这三块面板后结束游戏，可以获得 $1200$ 日元。

样例解释 2

你也可以选择一块面板都不翻开直接结束游戏。

由 ChatGPT 4.1 翻译