#cpsco2019s2b. [cpsco2019_s2_b]Telephone Q

[cpsco2019_s2_b]Telephone Q

問題文

夜のテレビ番組「こんばんはゴジラです」では、次のようなパネルめくりゲームを実施しています。

ゲームの参加者であるあなたは、初めに 00 円を持っています。

各パネルには記号と非負整数が 11 つずつ書かれており、 ii 番目のパネルに書かれた記号と非負整数はそれぞれ ci,aic_i, a_i です。

あなたが ii 番目のパネルを開けたとき、以下のルールに従ってあなたの所持金が変化します。

  • ci=c_i= + のとき:所持金が aia_i 円増える。
  • ci=c_i= - のとき:所持金が aia_i 円減る。
  • ci=c_i= * のとき:所持金が aia_i 倍になる。

あなたは、 NN 枚のパネルのうち 00 枚以上のパネルを、11 枚ずつ好きな順番で開けることができ、途中でいつでもゲームを終了することができます。また、ゲーム途中及び終了時に所持金が負の値になってもかまいません。

あらかじめどのパネルに何が書かれてあるかを知っているあなたは、ゲーム終了時の自分の所持金を最大化しようとしました。ゲーム終了時の所持金の最大値 MM を答えてください。

制約

  • 1leqNleq10001 \\leq N \\leq 1000
  • 0leqaileq10000 \\leq a_i \\leq 1000
  • cic_i+, -, * のいずれかである。
  • ゲーム終了時の所持金の最大値 MM10910^9 を超えない。

入力

入力は以下の形式で標準入力から与えられる。

NN c1c_1 a1a_1 :: cNc_N aNa_N

出力

ゲーム終了時の所持金の最大値 MM を出力せよ。


入力例 1

4
+ 100
- 80
* 3
+ 300

出力例 1

1200

+100+100 」,「 +300+300 」,「 \*3\*3 」のパネルを順に開けた後ゲームを終了することによって、 12001200 円を得ることができます。


入力例 2

3
- 314
- 159
- 265

出力例 2

11 枚もパネルを開かずにゲームを終了することもできます。


入力例 3

4
* 8
+ 7
* 0
* 5

出力例 2

280