#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define reep(i,a,b) for(int i=a; i<b; i++)
#define INF 0x3f3f3f3f

string s;
int mn[300][300];
int mx[300][300];

int MAX(int l, int r);
int MIN(int l, int r);


int MAX(int l, int r){
	if(mx[l][r]!=-INF) return mx[l][r];
	int &ret = mx[l][r];
	while(s[l] == '(') l++;
	while(s[r] == ')') r--;
	if(l==r&&isdigit(s[l])) return ret = s[l]-'0';
	if(s[l+1]==')') return ret;
	if(s[r-1]=='(') return ret;
	reep(i,l,r+1){
		if(s[i]=='+') ret = max(ret, MAX(l,i-1)+MAX(i+1, r));
		if(s[i]=='-') ret = max(ret, MAX(l,i-1)-MIN(i+1, r));
	}
	return ret;
}

int MIN(int l, int r){
	if(mn[l][r]!=INF) return mn[l][r];
	int &ret = mn[l][r];
	while(s[l] == '(') l++;
	while(s[r] == ')') r--;
	if(l==r&&isdigit(s[l])) return ret = s[l]-'0';
	if(s[l+1]==')') return ret;
	if(s[r-1]=='(') return ret;
	reep(i,l,r+1){
		if(s[i]=='+') ret = min(ret, MIN(l,i-1)+MIN(i+1, r));
		if(s[i]=='-') ret = min(ret, MIN(l,i-1)-MAX(i+1, r));
	}
	return ret;
}

int main(){
	cin>>s;
	rep(i,300){
		rep(j,300){
			mx[i][j] = -INF;
			mn[i][j] = INF;
		}
	}
	cout<<MAX(0,s.size()-1)<<endl;
}
### 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>

using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
#define reep(i,a,b) for(int i=a; i<b; i++)
#define INF 0x3f3f3f3f

string s;
int mn[300][300];
int mx[300][300];

int MAX(int l, int r);
int MIN(int l, int r);


int MAX(int l, int r){
	if(mx[l][r]!=-INF) return mx[l][r];
	int &ret = mx[l][r];
	while(s[l] == '(') l++;
	while(s[r] == ')') r--;
	if(l==r&&isdigit(s[l])) return ret = s[l]-'0';
	if(s[l+1]==')') return ret;
	if(s[r-1]=='(') return ret;
	reep(i,l,r+1){
		if(s[i]=='+') ret = max(ret, MAX(l,i-1)+MAX(i+1, r));
		if(s[i]=='-') ret = max(ret, MAX(l,i-1)-MIN(i+1, r));
	}
	return ret;
}

int MIN(int l, int r){
	if(mn[l][r]!=INF) return mn[l][r];
	int &ret = mn[l][r];
	while(s[l] == '(') l++;
	while(s[r] == ')') r--;
	if(l==r&&isdigit(s[l])) return ret = s[l]-'0';
	if(s[l+1]==')') return ret;
	if(s[r-1]=='(') return ret;
	reep(i,l,r+1){
		if(s[i]=='+') ret = min(ret, MIN(l,i-1)+MIN(i+1, r));
		if(s[i]=='-') ret = min(ret, MIN(l,i-1)-MAX(i+1, r));
	}
	return ret;
}

int main(){
	cin>>s;
	rep(i,300){
		rep(j,300){
			mx[i][j] = -INF;
			mn[i][j] = INF;
		}
	}
	cout<<MAX(0,s.size()-1)<<endl;
}
```