← 返回题目列表

Codeforces · 552/E

E. 万尼亚和括号

中文机器翻译题面 查看原题

Vanya 正在做数学作业。他有一个形式为 $$x_{1} \diamond x_{2} \diamond x_{3} \diamond \ldots \diamond x_{n}$$ 的表达式,其中 x1, x2, ..., xn 是从 1 到 9 的数字,符号 $$\text{ }$$ 代表加号“+”或乘号“*”。 Vanya 需要在该表达式中添加一对括号,以便最大化结果表达式的值。

输入

第一行包含表达式 s (1 ≤ |s| ≤ 5001,|s| 为奇数),其奇数位置仅包含 1 到 9 的数字,偶数位置仅包含符号 + 和 * 。

*号的个数不超过15个。

输出

在第一行打印表达式的最大可能值。

示例

输入 #1

3+5*7+8*4

输出 #1

303

输入 #2

2+3*5

输出 #2

25

输入 #3

3*4*5

输出 #3

60

注意

第一个样本测试注意事项。 3 + 5 * (7 + 8) * 4 = 303。

第二个样本测试注意事项。 (2 + 3) * 5 = 25。

第三个样本测试的注意事项。 (3 * 4) * 5 = 60(许多其他变体也是有效的,例如,(3) * 4 * 5 = 60)。