An Equation in a Mine

時間制限 : 2 sec, メモリ制限 : 262144 KB

坑道数式

ある日廃坑を探検していたあなたは、坑道に長い数式 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"

Constraints

  • 3 ≤ |S| ≤ 200

S は数式を表す。

Input Format

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

S

Output Format

答えを整数で出力せよ。

Sample Input 1

1-(2+3-4+5)

Sample Output 1

5

1-(2+3-(4+5))が最大となる。

Sample Input 2

1-(2+3+4)

Sample Output 2

0

(1-(2+3)+4)が最大となる。

Sample Input 3

1-(2+3)

Sample Output 3

-4

1-(2)+(3)はここでいう数式ではないことに注意。


Source: ACM-ICPC Japan Alumni Group Summer Camp 2015 , Day 2, Tokyo, Japan, 2015-09-12
http://acm-icpc.aitea.net/
http://jag2015summer-day2.contest.atcoder.jp/