#include <bits/stdc++.h>
#define INF (1e9)
using namespace std;


int calc(string s){
  vector<int> v;
  for(int i=0;i<s.size();i++){
    int n = (int)v.size()-1;
    if(s[i]=='+')v.push_back(0);
    if(s[i]=='-')v.push_back(1);
    if(s[i]=='(')v.push_back(0),v.push_back(0);
    if(s[i]==')'){
      if(v.size()<3)continue;
      v[n-2]+=v[n-1]? -v[n]:v[n];
      v.pop_back(),v.pop_back();
    }

    if(isdigit(s[i])){
      int num=s[i]-'0';
      if(v.size()>=2){
	v[n-1]+=v[n]? -num:num;
	v.pop_back();
      }
      else v.push_back(num);
    }
  }
  return v[0];
}


bool check(string s){
  if(s[0]!='(')return 0;
  int i=1,c=1;
  while(c)c+=(s[i]=='(')-(s[i++]==')');
  return i==(int)s.size();
}


map<string,int> mem[2];
int dfs(string s,int f){
  while(check(s))s=s.substr(1,s.size()-2);
  if(s.size()==1) return s[0]-'0';
  if(mem[f].count(s))return mem[f][s];
  
  int n=s.size(),res=calc(s),d=0;
  for(int i=0;i<n;i++) if(s[i]=='+'||s[i]=='-')d++;
  for(int i=0,c=0,cnt=0;i<n;i++,cnt++,d--){
    while(i<n){
      while(s[i]=='('||s[i]==')')c+=(s[i]=='(')-(s[i]==')'),i++;
      if(s[i]=='+'||s[i]=='-') break;
      i++;
    }
    if(i>=n)break;
    if(cnt&&s[i-2]=='(')continue;
    if(d!=1&&s[i+2]==')')continue;
    string a=s.substr(0,i),b=s.substr(i+1,n-i-1);
    int t=c,ch=s[i];
    while(t--)a+=')',b='('+b;
    int mxa=dfs(a,0),mna=dfs(a,1);
    int mxb=dfs(b,0),mnb=dfs(b,1);
    if(f==0&&ch=='+') res=max(res, mxa+mxb);
    if(f==0&&ch=='-') res=max(res, mxa-mnb);
    if(f==1&&ch=='+') res=min(res, mna+mnb);
    if(f==1&&ch=='-') res=min(res, mna-mxb);
  }
  return mem[f][s]=res;
}




int main(){
  string S;
  cin>>S;

  cout <<dfs(S,0)<<endl;
  return 0;
}
### Prompt

Develop a solution in Cpp 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 <bits/stdc++.h>
#define INF (1e9)
using namespace std;


int calc(string s){
  vector<int> v;
  for(int i=0;i<s.size();i++){
    int n = (int)v.size()-1;
    if(s[i]=='+')v.push_back(0);
    if(s[i]=='-')v.push_back(1);
    if(s[i]=='(')v.push_back(0),v.push_back(0);
    if(s[i]==')'){
      if(v.size()<3)continue;
      v[n-2]+=v[n-1]? -v[n]:v[n];
      v.pop_back(),v.pop_back();
    }

    if(isdigit(s[i])){
      int num=s[i]-'0';
      if(v.size()>=2){
	v[n-1]+=v[n]? -num:num;
	v.pop_back();
      }
      else v.push_back(num);
    }
  }
  return v[0];
}


bool check(string s){
  if(s[0]!='(')return 0;
  int i=1,c=1;
  while(c)c+=(s[i]=='(')-(s[i++]==')');
  return i==(int)s.size();
}


map<string,int> mem[2];
int dfs(string s,int f){
  while(check(s))s=s.substr(1,s.size()-2);
  if(s.size()==1) return s[0]-'0';
  if(mem[f].count(s))return mem[f][s];
  
  int n=s.size(),res=calc(s),d=0;
  for(int i=0;i<n;i++) if(s[i]=='+'||s[i]=='-')d++;
  for(int i=0,c=0,cnt=0;i<n;i++,cnt++,d--){
    while(i<n){
      while(s[i]=='('||s[i]==')')c+=(s[i]=='(')-(s[i]==')'),i++;
      if(s[i]=='+'||s[i]=='-') break;
      i++;
    }
    if(i>=n)break;
    if(cnt&&s[i-2]=='(')continue;
    if(d!=1&&s[i+2]==')')continue;
    string a=s.substr(0,i),b=s.substr(i+1,n-i-1);
    int t=c,ch=s[i];
    while(t--)a+=')',b='('+b;
    int mxa=dfs(a,0),mna=dfs(a,1);
    int mxb=dfs(b,0),mnb=dfs(b,1);
    if(f==0&&ch=='+') res=max(res, mxa+mxb);
    if(f==0&&ch=='-') res=max(res, mxa-mnb);
    if(f==1&&ch=='+') res=min(res, mna+mnb);
    if(f==1&&ch=='-') res=min(res, mna-mxb);
  }
  return mem[f][s]=res;
}




int main(){
  string S;
  cin>>S;

  cout <<dfs(S,0)<<endl;
  return 0;
}
```