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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e7;

int dp[210][210][2];
bool isl[210], isr[210];
string S;
int N;

int solve(int l, int r, int f){
  if(dp[l][r][f] != MOD) return dp[l][r][f];

  int& res = dp[l][r][f];
  res = f? -INF: INF;
  if(l+1 == r){
	if(!isl[l] && !isr[l])
	  res = S[l] - '0';
	return res;
  }

  bool pl = isl[l];
  bool pr = isr[r-1];
  isl[l] = isr[r-1] = false;
  for(int i=l+1;i<r-1;i+=2){
	if(isl[i-1] || isr[i+1]) continue;
	if(S[i] == '+'){
	  if(f)
		maxi(res, solve(l,i,1) + solve(i+1,r,1));
	  else
		mini(res, solve(l,i,0) + solve(i+1,r,0));
	}
	else if(S[i] == '-'){
	  if(f)
		maxi(res, solve(l,i,1) - solve(i+1,r,0));
	  else
		mini(res, solve(l,i,0) - solve(i+1,r,1));
	}
  }
  isl[l] = pl;
  isr[r-1] = pr;
  
  return res;
}


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string tmp;
  cin >> tmp;

  int j = 0;
  for(int i=0;i<SZ(tmp);++i){
	if(tmp[i] == '('){
	  isl[j] = true;
	}
	else if(tmp[i] == ')'){
	  isr[j-1] = true;
	}
	else{
	  S += string(1, tmp[i]);
	  ++j;
	}
  }
  N = SZ(S);

  fill((int*)dp, (int*)dp+210*210*2, MOD);
  cout << solve(0, N, 1) << endl;

  return 0;
}
### Prompt

Your challenge is to write a cpp solution to 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;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e7;

int dp[210][210][2];
bool isl[210], isr[210];
string S;
int N;

int solve(int l, int r, int f){
  if(dp[l][r][f] != MOD) return dp[l][r][f];

  int& res = dp[l][r][f];
  res = f? -INF: INF;
  if(l+1 == r){
	if(!isl[l] && !isr[l])
	  res = S[l] - '0';
	return res;
  }

  bool pl = isl[l];
  bool pr = isr[r-1];
  isl[l] = isr[r-1] = false;
  for(int i=l+1;i<r-1;i+=2){
	if(isl[i-1] || isr[i+1]) continue;
	if(S[i] == '+'){
	  if(f)
		maxi(res, solve(l,i,1) + solve(i+1,r,1));
	  else
		mini(res, solve(l,i,0) + solve(i+1,r,0));
	}
	else if(S[i] == '-'){
	  if(f)
		maxi(res, solve(l,i,1) - solve(i+1,r,0));
	  else
		mini(res, solve(l,i,0) - solve(i+1,r,1));
	}
  }
  isl[l] = pl;
  isr[r-1] = pr;
  
  return res;
}


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string tmp;
  cin >> tmp;

  int j = 0;
  for(int i=0;i<SZ(tmp);++i){
	if(tmp[i] == '('){
	  isl[j] = true;
	}
	else if(tmp[i] == ')'){
	  isr[j-1] = true;
	}
	else{
	  S += string(1, tmp[i]);
	  ++j;
	}
  }
  N = SZ(S);

  fill((int*)dp, (int*)dp+210*210*2, MOD);
  cout << solve(0, N, 1) << endl;

  return 0;
}
```