ある日廃坑を探検していたあなたは、坑道に長い数式 S が書かれているのを発見した。大きな数が好きなあなたは、チョークを取り出し、数式を計算した結果ができるだけ大きくなるように(
または)
を書き加えることにした。書き加えた後も数式になっていなければならないとすると、最大でいくつにできるか。
文字と文字の間は十分広く空いていて、(
または)
であればいくつでも書き加えることができる。最終的に数式になっていれば、最初のかっこの対応が崩れるように(
または)
を書いてもよい(Sample 2参照)。
また、ここでは以下のBNFで定義される<expr>を数式と呼ぶ。数式中の数は全て一桁である。
<expr> ::= "(" <expr> ")" | <term> "+" <term> | <term> "-" <term> <term> ::= <digit> | <expr> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
S は数式を表す。
入力は以下の形式で標準入力から与えられる。
S
答えを整数で出力せよ。
1-(2+3-4+5)
5
1-(2+3-(4+5))が最大となる。
1-(2+3+4)
0
(1-(2+3)+4)が最大となる。
1-(2+3)
-4
1-(2)+(3)はここでいう数式ではないことに注意。