解题思路

这题的关键是发现可以用“贪心 $+$ 单调性”解决。

设当前权值为 $v$，一扇门的操作结果记为 $f(v)$，另一扇门的操作结果记为 $g(v)$。

每一关之后，后面的所有操作都是基于“当前权值”继续进行的。 如果后续最优结果函数记为 $F(v)$，那么因为题目的四种操作：

题目内容

笨蛋同学在闯关游戏，她的初始权值为 $1$ 。接下来她会经历 $n$ 关，每一关有两扇门，她必须从两扇门中选择一扇进入。

每扇门上都写有一个运算操作，通过这扇门时，她的权值会进行相应的运算。

门上的运算操作可能是以下四种之一：

• $+x$：将权值增加 $x$。
• $−x$：将权值减少 $x$。
• $∗x$：将权值乘 $x$。
• $/x$：将权值整除 $x$（向下取整）。

由于游戏的限制，她的权值将始终被限制在 $1$ 到 $10^9$ 之间。具体来说，如果某次操作后权值小于 $1$，则权值变为 $1$；如果权值大于 $10^9$，则权值变为 $10^9$。

笨蛋同学想知道她穿过所有 $n$ 个黑暗之门后的最大权值是多少。

输入描述

第一行输入一个正整数 $n（1≤n≤2×10^5）$，表示有 $n$ 关。

接下来 $n$ 行，每行描述这一关的两扇门。每组操作由一个字符 $op$（'$+$'、'$−$'、'$∗$' 或 '$/$'）和一个整数 $x（1≤x≤10^9）$ 组成。

输出描述

输出一个整数，表示穿过所有关卡后可能达到的最大权值。

样例1

输入

3
+ 10 * 2
* 2 / 5
- 5 / 2

输出

17

说明

• 初始权值为 $1$。
• 第 $1$ 关：选择 '$+10$'，权值变为 $11$。
• 第 $2$ 关：选择 '$∗2$'，权值变为 $22$。
• 第 $3$ 关：选择 '$−5$'，权值变为 $17$。

最终最大权值为 $17$ 。

样例2

输入

3
- 10 * 1
* 2 / 100
/ 2 + 1000

输出

1002