#include <bits/stdc++.h>
using namespace std;

int dp[201][201][2];

int main() {
  string s;
  cin >> s;
  for(int i=0; i<s.size(); i++) {
    for(int j=0; j<s.size(); j++) {
      dp[i][j][0]=1<<29;
      dp[i][j][1]=-(1<<29);
    }
    if(isdigit(s[i])) dp[i][i][0]=dp[i][i][1]=s[i]-'0';
  }
  for(int i=1; i<s.size(); i++) {
    for(int j=0; j<s.size()-i; j++) {
      if(s[j]=='(') {
        dp[j][j+i][0]=min(dp[j][j+i][0],dp[j+1][j+i][0]);
        dp[j][j+i][1]=max(dp[j][j+i][1],dp[j+1][j+i][1]);
      }
      if(s[j+i]==')') {
        dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][j+i-1][0]);
        dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][j+i-1][1]);
      }
    }
    for(int j=0; j<s.size()-i; j++) {
      if(s[j]=='+'||s[j]=='-'||s[j+i]=='+'||s[j+i]=='-') continue;
      for(int k=j+1; k<=j+i-1; k++) {
        if((j+2<=k&&s[k-2]=='(')||(k<=j+i-2&&s[k+2]==')')) continue;
        if(s[k]=='+') {
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][k-1][x]+dp[k+1][j+i][y]);
            }
          }
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][k-1][x]+dp[k+1][j+i][y]);
            }
          }
        } else if(s[k]=='-') {
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][k-1][x]-dp[k+1][j+i][y]);
            }
          }
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][k-1][x]-dp[k+1][j+i][y]);
            }
          }
        }
      }
    }
  }
  cout << dp[0][s.size()-1][1] << endl;
  return 0;
}
### Prompt

Create a solution in Cpp for the following problem:

Tunnel formula

One day while exploring an abandoned mine, you found a long formula S written in the mine. If you like large numbers, you decide to take out the choke and add `(` or `)` so that the result of the formula calculation is as large as possible. If it has to be a mathematical formula even after adding it, how many can it be at the maximum?

There is enough space between the letters, and you can add as many `(` or `)` as you like. If the final formula is a formula, you may write `(` or `)` so that the correspondence of the first parenthesis is broken (see Sample 2). Also, here, <expr> defined by the following BNF is called a mathematical formula. All numbers in the formula are single digits.


<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 represents a mathematical formula.

Input Format

Input is given from standard input in the following format.


S


Output Format

Output the answer as an integer.

Sample Input 1


1- (2 + 3-4 + 5)


Sample Output 1


Five


1- (2 + 3- (4 + 5)) is the maximum.

Sample Input 2


1- (2 + 3 + 4)


Sample Output 2


0


(1- (2 + 3) + 4) is the maximum.

Sample Input 3


1- (2 + 3)


Sample Output 3


-Four


Note that 1- (2) + (3) is not the formula here.





Example

Input

1-(2+3-4+5)


Output

5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

int dp[201][201][2];

int main() {
  string s;
  cin >> s;
  for(int i=0; i<s.size(); i++) {
    for(int j=0; j<s.size(); j++) {
      dp[i][j][0]=1<<29;
      dp[i][j][1]=-(1<<29);
    }
    if(isdigit(s[i])) dp[i][i][0]=dp[i][i][1]=s[i]-'0';
  }
  for(int i=1; i<s.size(); i++) {
    for(int j=0; j<s.size()-i; j++) {
      if(s[j]=='(') {
        dp[j][j+i][0]=min(dp[j][j+i][0],dp[j+1][j+i][0]);
        dp[j][j+i][1]=max(dp[j][j+i][1],dp[j+1][j+i][1]);
      }
      if(s[j+i]==')') {
        dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][j+i-1][0]);
        dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][j+i-1][1]);
      }
    }
    for(int j=0; j<s.size()-i; j++) {
      if(s[j]=='+'||s[j]=='-'||s[j+i]=='+'||s[j+i]=='-') continue;
      for(int k=j+1; k<=j+i-1; k++) {
        if((j+2<=k&&s[k-2]=='(')||(k<=j+i-2&&s[k+2]==')')) continue;
        if(s[k]=='+') {
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][k-1][x]+dp[k+1][j+i][y]);
            }
          }
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][k-1][x]+dp[k+1][j+i][y]);
            }
          }
        } else if(s[k]=='-') {
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][0]=min(dp[j][j+i][0],dp[j][k-1][x]-dp[k+1][j+i][y]);
            }
          }
          for(int x=0; x<2; x++) {
            for(int y=0; y<2; y++) {
              if(abs(dp[j][k-1][x])>=(1<<29)||abs(dp[k+1][j+i][y])>=(1<<29)) continue;
              dp[j][j+i][1]=max(dp[j][j+i][1],dp[j][k-1][x]-dp[k+1][j+i][y]);
            }
          }
        }
      }
    }
  }
  cout << dp[0][s.size()-1][1] << endl;
  return 0;
}
```