#include<iostream>
#include<cstdio>
#include<climits>
#include<cassert>
#include<cstring>
#include<sstream>
#include<bitset>
#include<deque>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<set>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define MAX 210
#define MINI 0
#define MAXI 1
long long dp[MAX][MAX][2];

int getPos(string &text,int p) {
  int cnt = 0;
  rep(i,(int)text.size()) {
    if( isdigit(text[i]) ) {
      if( cnt == p ) return i;
      ++cnt;
    }
  }
  assert(false);
}

void fix(string &text,string &L,string &R) {
  string tmp = text;
  rep(i,(int)text.size()) {
    if( text[i] == '(' || text[i] == ')' ) {
      text[i] = ' ';
    }
  }
  {
    stringstream ss;
    ss << text;
    string new_text = "";
    while( ss >> text ) new_text += text;
    text = new_text;
  }
  L = R = string((int)text.size(),'o');
  for(int i=0;i<(int)text.size();i+=2) {
    assert( isdigit(text[i]) );
    int p = getPos(tmp,i/2);
    if( p - 1 >= 0 && tmp[p-1] == '(' ) L[i] = 'x';
    if( p + 1 < (int)tmp.size() && tmp[p+1] == ')' ) R[i] = 'x';
  }
}

void compute(string text) {
  string L,R;
  fix(text,L,R);
  /*
  cout << "new text = " << text << endl;
  cout << "L        = " << L << endl;
  cout << "R        = " << R << endl;
  */
  rep(i,MAX) rep(j,MAX) dp[i][j][MINI] = INT_MAX;
  rep(i,MAX) rep(j,MAX) dp[i][j][MAXI] = -INT_MAX;
  rep(i,(int)text.size()) if( isdigit(text[i]) ) {
    dp[i][i][MINI] = dp[i][i][MAXI] = text[i] - '0';
  }
  int n = ((int)text.size()+1) / 2;
  REP(i,2,n+1) {
    for(int j=0;j<(int)text.size();j+=2) {
      int k = j + ( i -1 ) * 2;
      if( k >= (int)text.size() ) break;
      if( L[k] == 'x' || R[j] == 'x' ) continue;
      for(int l=j+1;l<(int)k;l+=2) {
	if( text[l] == '+' ) {
	  if( dp[j][l-1][MINI] != INT_MAX && dp[l+1][k][MINI] != INT_MAX ) {
	    dp[j][k][MINI] = min(dp[j][k][MINI],
				 dp[j][l-1][MINI]+dp[l+1][k][MINI]);
	  }
	  if( dp[j][l-1][MAXI] != -INT_MAX && dp[l+1][k][MAXI] != -INT_MAX ) {
	    dp[j][k][MAXI] = max(dp[j][k][MAXI],
				 dp[j][l-1][MAXI]+dp[l+1][k][MAXI]);
	  }
	} else {
	  if( dp[j][l-1][MINI] != INT_MAX && dp[l+1][k][MAXI] != -INT_MAX ) {
	    dp[j][k][MINI] = min(dp[j][k][MINI],
				 dp[j][l-1][MINI]-dp[l+1][k][MAXI]);
	  }
	  if( dp[j][l-1][MAXI] != -INT_MAX && dp[l+1][k][MINI] != INT_MAX ) {
	    dp[j][k][MAXI] = max(dp[j][k][MAXI],
				 dp[j][l-1][MAXI]-dp[l+1][k][MINI]);
	  }
	}
      }
    }
  }
  cout << dp[0][(int)text.size()-1][MAXI] << endl;
}

int main() {
  string text;
  cin >> text;
  compute(text);
  return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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<iostream>
#include<cstdio>
#include<climits>
#include<cassert>
#include<cstring>
#include<sstream>
#include<bitset>
#include<deque>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<set>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define MAX 210
#define MINI 0
#define MAXI 1
long long dp[MAX][MAX][2];

int getPos(string &text,int p) {
  int cnt = 0;
  rep(i,(int)text.size()) {
    if( isdigit(text[i]) ) {
      if( cnt == p ) return i;
      ++cnt;
    }
  }
  assert(false);
}

void fix(string &text,string &L,string &R) {
  string tmp = text;
  rep(i,(int)text.size()) {
    if( text[i] == '(' || text[i] == ')' ) {
      text[i] = ' ';
    }
  }
  {
    stringstream ss;
    ss << text;
    string new_text = "";
    while( ss >> text ) new_text += text;
    text = new_text;
  }
  L = R = string((int)text.size(),'o');
  for(int i=0;i<(int)text.size();i+=2) {
    assert( isdigit(text[i]) );
    int p = getPos(tmp,i/2);
    if( p - 1 >= 0 && tmp[p-1] == '(' ) L[i] = 'x';
    if( p + 1 < (int)tmp.size() && tmp[p+1] == ')' ) R[i] = 'x';
  }
}

void compute(string text) {
  string L,R;
  fix(text,L,R);
  /*
  cout << "new text = " << text << endl;
  cout << "L        = " << L << endl;
  cout << "R        = " << R << endl;
  */
  rep(i,MAX) rep(j,MAX) dp[i][j][MINI] = INT_MAX;
  rep(i,MAX) rep(j,MAX) dp[i][j][MAXI] = -INT_MAX;
  rep(i,(int)text.size()) if( isdigit(text[i]) ) {
    dp[i][i][MINI] = dp[i][i][MAXI] = text[i] - '0';
  }
  int n = ((int)text.size()+1) / 2;
  REP(i,2,n+1) {
    for(int j=0;j<(int)text.size();j+=2) {
      int k = j + ( i -1 ) * 2;
      if( k >= (int)text.size() ) break;
      if( L[k] == 'x' || R[j] == 'x' ) continue;
      for(int l=j+1;l<(int)k;l+=2) {
	if( text[l] == '+' ) {
	  if( dp[j][l-1][MINI] != INT_MAX && dp[l+1][k][MINI] != INT_MAX ) {
	    dp[j][k][MINI] = min(dp[j][k][MINI],
				 dp[j][l-1][MINI]+dp[l+1][k][MINI]);
	  }
	  if( dp[j][l-1][MAXI] != -INT_MAX && dp[l+1][k][MAXI] != -INT_MAX ) {
	    dp[j][k][MAXI] = max(dp[j][k][MAXI],
				 dp[j][l-1][MAXI]+dp[l+1][k][MAXI]);
	  }
	} else {
	  if( dp[j][l-1][MINI] != INT_MAX && dp[l+1][k][MAXI] != -INT_MAX ) {
	    dp[j][k][MINI] = min(dp[j][k][MINI],
				 dp[j][l-1][MINI]-dp[l+1][k][MAXI]);
	  }
	  if( dp[j][l-1][MAXI] != -INT_MAX && dp[l+1][k][MINI] != INT_MAX ) {
	    dp[j][k][MAXI] = max(dp[j][k][MAXI],
				 dp[j][l-1][MAXI]-dp[l+1][k][MINI]);
	  }
	}
      }
    }
  }
  cout << dp[0][(int)text.size()-1][MAXI] << endl;
}

int main() {
  string text;
  cin >> text;
  compute(text);
  return 0;
}
```