#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
const int inf=1<<20;

int num[210];
char op[210];
bool lb[210],rb[210];

int memo[210][210][2];

int rec(int l,int r){
	if(r-l==1) return memo[l][r][0]=memo[l][r][1]=num[l];

	if(lb[r-1]) return -inf;
	if(rb[l]) return -inf;
	
	int &cmin=memo[l][r][0];
	int &cmax=memo[l][r][1];
	if(cmax!=-inf) return cmax;

	rep(m,l+1,r){
		int a=rec(l,m),b=rec(m,r);
		if(a==-inf||b==-inf) continue;
		if(op[m]=='+'){
			chmax(cmax,memo[l][m][1]+memo[m][r][1]);
			chmin(cmin,memo[l][m][0]+memo[m][r][0]);
		}else{
			chmax(cmax,memo[l][m][1]-memo[m][r][0]);
			chmin(cmin,memo[l][m][0]-memo[m][r][1]);
		}
	}

	return cmax;
}


int main(void){
	string s;
	cin >> s;

	int tidx=0,oidx=1;
	for(auto &c:s){
		if(c=='(') lb[tidx]=true;
		if(c==')') rb[tidx-1]=true;
		if(isdigit(c)) num[tidx++]=c-'0';
		if(c=='+'||c=='-') op[oidx++]=c;
	}

	// rep(i,5) cout << num[i] << " " << lb[i] << " " << rb[i] << endl;
	// rep(i,1,5) cout << op[i] << endl;

	rep(i,210)rep(j,210) memo[i][j][0]=inf,memo[i][j][1]=-inf;
	cout << rec(0,tidx) << endl;

	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 <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
const int inf=1<<20;

int num[210];
char op[210];
bool lb[210],rb[210];

int memo[210][210][2];

int rec(int l,int r){
	if(r-l==1) return memo[l][r][0]=memo[l][r][1]=num[l];

	if(lb[r-1]) return -inf;
	if(rb[l]) return -inf;
	
	int &cmin=memo[l][r][0];
	int &cmax=memo[l][r][1];
	if(cmax!=-inf) return cmax;

	rep(m,l+1,r){
		int a=rec(l,m),b=rec(m,r);
		if(a==-inf||b==-inf) continue;
		if(op[m]=='+'){
			chmax(cmax,memo[l][m][1]+memo[m][r][1]);
			chmin(cmin,memo[l][m][0]+memo[m][r][0]);
		}else{
			chmax(cmax,memo[l][m][1]-memo[m][r][0]);
			chmin(cmin,memo[l][m][0]-memo[m][r][1]);
		}
	}

	return cmax;
}


int main(void){
	string s;
	cin >> s;

	int tidx=0,oidx=1;
	for(auto &c:s){
		if(c=='(') lb[tidx]=true;
		if(c==')') rb[tidx-1]=true;
		if(isdigit(c)) num[tidx++]=c-'0';
		if(c=='+'||c=='-') op[oidx++]=c;
	}

	// rep(i,5) cout << num[i] << " " << lb[i] << " " << rb[i] << endl;
	// rep(i,1,5) cout << op[i] << endl;

	rep(i,210)rep(j,210) memo[i][j][0]=inf,memo[i][j][1]=-inf;
	cout << rec(0,tidx) << endl;

	return 0;
}
```