#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
Def inf = sizeof(Def)==sizeof(ll)?2e18:1e9+10;
int n,co;
vvi w;
string s,t;
int dp[110][110][2];//min max
int dfs(int l,int r,int c){
	if(c&&dp[l][r][c]!=-inf)return dp[l][r][c];
	if(!c&&dp[l][r][c]!=inf)return dp[l][r][c];
	
	int out=inf;
	if(c)out=-inf;
	if(l==r)return t[l]-'0';
	if(w[l][1]||w[r][0])return inf;
	loop(i,l,r){
		int a,b;
		if(c){
			a=dfs(l,i,1);
			if(w[i+1][2]==0)b=dfs(i+1,r,1);
			else b=-dfs(i+1,r,0);
		}else{
			a=dfs(l,i,0);
			if(w[i+1][2]==0)b=dfs(i+1,r,0);
			else b=-dfs(i+1,r,1);
		}
		if(abs(a)==inf||abs(b)==inf)continue;
		if(c)out=max(out,a+b);
		else out=min(out,a+b);
	}
//	cout<<l<<" "<<r<<" "<<c<<" "<<out<<endl;
	return dp[l][r][c]=out;
}
int main(){
	cin>>s;
	n=s.size();
	int co=0;
	rep(i,n)if(isdigit(s[i]))co++;
	w=vvi(co,vi(3));
	t="";
	rep(i,s.size()){
		if(s[i]=='('){
			w[t.size()][0]=true;
		}else if(s[i]==')'){
			w[t.size()-1][1]=true;
		}else if(isdigit(s[i])){
			t+=s[i];
		}else if(s[i]=='-'){
			w[t.size()][2]=true;
		}
	}
	rep(i,110)rep(j,110){
		dp[i][j][0]=inf;
		dp[i][j][1]=-inf;
	}
//	cout<<t<<endl;
//	show2d(w);
	cout<<dfs(0,co-1,1)<<endl;
}












### Prompt

Please provide a cpp coded solution 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<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
Def inf = sizeof(Def)==sizeof(ll)?2e18:1e9+10;
int n,co;
vvi w;
string s,t;
int dp[110][110][2];//min max
int dfs(int l,int r,int c){
	if(c&&dp[l][r][c]!=-inf)return dp[l][r][c];
	if(!c&&dp[l][r][c]!=inf)return dp[l][r][c];
	
	int out=inf;
	if(c)out=-inf;
	if(l==r)return t[l]-'0';
	if(w[l][1]||w[r][0])return inf;
	loop(i,l,r){
		int a,b;
		if(c){
			a=dfs(l,i,1);
			if(w[i+1][2]==0)b=dfs(i+1,r,1);
			else b=-dfs(i+1,r,0);
		}else{
			a=dfs(l,i,0);
			if(w[i+1][2]==0)b=dfs(i+1,r,0);
			else b=-dfs(i+1,r,1);
		}
		if(abs(a)==inf||abs(b)==inf)continue;
		if(c)out=max(out,a+b);
		else out=min(out,a+b);
	}
//	cout<<l<<" "<<r<<" "<<c<<" "<<out<<endl;
	return dp[l][r][c]=out;
}
int main(){
	cin>>s;
	n=s.size();
	int co=0;
	rep(i,n)if(isdigit(s[i]))co++;
	w=vvi(co,vi(3));
	t="";
	rep(i,s.size()){
		if(s[i]=='('){
			w[t.size()][0]=true;
		}else if(s[i]==')'){
			w[t.size()-1][1]=true;
		}else if(isdigit(s[i])){
			t+=s[i];
		}else if(s[i]=='-'){
			w[t.size()][2]=true;
		}
	}
	rep(i,110)rep(j,110){
		dp[i][j][0]=inf;
		dp[i][j][1]=-inf;
	}
//	cout<<t<<endl;
//	show2d(w);
	cout<<dfs(0,co-1,1)<<endl;
}












```