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

#define int long long
using P = pair<int, int>;
const int INF = 1e9;

string s;
vector<vector<P> > dp;

P dfs(int l, int r) {
  if ( dp[l][r] != P(-INF, INF) ) {
    return dp[l][r];    
  }
  if ( l == r ) {
    return P(s[l]-'0', s[l]-'0');    
  }

  P ret = {-INF, INF};
  if ( s[l] == '(' && r-l >= 3 ) {
    P res = dfs(l+1, r);
    ret.first = max(ret.first, res.first);
    ret.second = min(ret.second, res.second);    
  }
  
  if ( s[r] == ')' && r-l >= 3 ) {
    P res = dfs(l, r-1);
    ret.first = max(ret.first, res.first);
    ret.second = min(ret.second, res.second);    
  }
  
  for ( int i = l+1; i < r; i++ ) {
    if ( s[i] == '+' ) {
      P res1 = dfs(l, i-1);
      P res2 = dfs(i+1, r);      
      ret.first = max(ret.first, res1.first+res2.first);
      ret.second = min(ret.second, res1.second+res2.second);      
    }
    if ( s[i] == '-' ) {
      P res1 = dfs(l, i-1);
      P res2 = dfs(i+1, r);      
      ret.first = max(ret.first, res1.first-res2.second);
      ret.second = min(ret.second, res1.second-res2.first);      
    }
  }

  return dp[l][r] = ret;  
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> s;

  int n = s.size();
  dp = vector<vector<P> >(n+1, vector<P>(n+1, P(-INF, INF)));

  cout << dfs(0, n-1).first << endl;  
  
  return 0;
}


### Prompt

Develop a solution in cpp to the problem described below:

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;

#define int long long
using P = pair<int, int>;
const int INF = 1e9;

string s;
vector<vector<P> > dp;

P dfs(int l, int r) {
  if ( dp[l][r] != P(-INF, INF) ) {
    return dp[l][r];    
  }
  if ( l == r ) {
    return P(s[l]-'0', s[l]-'0');    
  }

  P ret = {-INF, INF};
  if ( s[l] == '(' && r-l >= 3 ) {
    P res = dfs(l+1, r);
    ret.first = max(ret.first, res.first);
    ret.second = min(ret.second, res.second);    
  }
  
  if ( s[r] == ')' && r-l >= 3 ) {
    P res = dfs(l, r-1);
    ret.first = max(ret.first, res.first);
    ret.second = min(ret.second, res.second);    
  }
  
  for ( int i = l+1; i < r; i++ ) {
    if ( s[i] == '+' ) {
      P res1 = dfs(l, i-1);
      P res2 = dfs(i+1, r);      
      ret.first = max(ret.first, res1.first+res2.first);
      ret.second = min(ret.second, res1.second+res2.second);      
    }
    if ( s[i] == '-' ) {
      P res1 = dfs(l, i-1);
      P res2 = dfs(i+1, r);      
      ret.first = max(ret.first, res1.first-res2.second);
      ret.second = min(ret.second, res1.second-res2.first);      
    }
  }

  return dp[l][r] = ret;  
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> s;

  int n = s.size();
  dp = vector<vector<P> >(n+1, vector<P>(n+1, P(-INF, INF)));

  cout << dfs(0, n-1).first << endl;  
  
  return 0;
}


```