坑道数式

시간 제한2초메모리 제한512 MB

요약

숫자열에 괄호를 원하는 만큼 넣어 표준 우선순위로 계산한 값이 최대가 되도록 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 구현, 재귀
정답자: 아직 제출이 없습니다

문제

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

출력

答えを整数で出力せよ。

제한

$3 \leq |S| \leq 200$

예제3

예제 1
입력
```
1-(2+3-4+5)
```
예상 출력
```
5
```
예제 2
입력
```
1-(2+3+4)
```
예상 출력
```
0
```
예제 3
입력
```
1-(2+3)
```
예상 출력
```
-4
```