Unordered Operators

Time Limit : 2 sec, Memory Limit : 131072 KB

小学生のイクタ君は、ある日おじいさんから数式が書かれた紙をもらった。 どうやらおじいさんは数式の答えの金額だけお小遣いをくれるらしい。 イクタ君はまだ足し算、引き算、掛け算しか習ってなかったので、数式にも足し算と引き算と掛け算しか使われていない。 通常の計算では足し算と引き算より掛け算を先に計算しなければならないのだが、イクタ君は演算子の優先順位についての理解があやふやだったので、とりあえず数式の計算結果が最大になるような都合の良い優先順位を考えることにした。

+−×の3つの二項演算子と括弧を含む数式が与えられる。 3つの演算子の優先順位を任意に変更して、数式を最大化したときの計算結果を答えよ。

ただし、以下の点に注意せよ。

  • 演算子は必ず左結合である。 (同じ優先順位の演算子は必ず数式の左側から計算する。)
  • 異なる演算子が同じ優先順位であってもよい。
  • 一つの数式を計算している途中で優先順位を変更してはならない。

Input

入力は以下の形式で与えられる。
0〜9の数字と演算子'+','-','*'、括弧'(',')'で構成された数式

  • 正確に記述すると入力は以下のBNFで示される形式になっている
<expr> ::= ( <expr> ) | <number> | <expr> <op> <expr>
<op> ::= + | - | *

<number>は非負整数を表す。

Constraints

入力は以下の制約を満たす。

  • 数式は200文字以下である。
  • どのような優先順位を設定しても、計算の結果やその途中で64bit整数型でoverflowするようなことはない。

Output

数式から得られる最大値を1行で出力せよ。

Sample Input 1

3-2*3

Output for the Sample Input 1

3
  • *の優先順位を-より低くすることでこのようになる。

Sample Input 2

(5-3*4)*(0-2+1)

Output for the Sample Input 2

21
  • 優先順位は+>*>-

Sample Input 3

1-2+3-4+5-6*0

Output for the Sample Input 3

3
  • 優先順位が一般的な場合

Sample Input 4

(1989967-3*1-211+4487)

Output for the Sample Input 4

8511076028

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 3, Tokyo, Japan, 2013-09-22
http://acm-icpc.aitea.net/
http://jag2013summer-day3.contest.atcoder.jp/