#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int n;
int used[300][300];
int dp[300][300];
int dfs(int p,int d){
  if(used[p][d]) return dp[p][d];
  used[p][d]=1;
  int res=-(1LL<<55LL),op=0;
  int j;
  for(j=p-1;j>=0;j--) if(s[j]=='+'||s[j]=='-') break;
  if(j>=0&&s[j]=='-') op=1;
  int x=((d+op)%2?-(s[p]-'0'):(s[p]-'0'));
  for(j=p+1;j<n;j++) if(isdigit(s[j])) break;
  if(j==n){
    //cout<<p<<" "<<d<<":"<<res<<"/"<<x<<endl;
    return dp[p][d]=x;
  }
  if(p<1||s[p-1]!='(') res=max(res,dfs(j,d)+x);
  if(p+1<n&&s[p+1]!=')') res=max(res,dfs(j,d+op)+x);
  if(d>0&&p-1>=0&&s[p-1]!='(') res=max(res,dfs(j,d-1)+x);
  //cout<<p<<" "<<d<<":"<<res<<"/"<<x<<endl;
  return dp[p][d]=res;
}
signed main(){
  cin>>s;
  n=s.length();
  int j;
  for(j=0;j<n;j++) if(isdigit(s[j])) break;
  cout<<dfs(j,0)<<endl;
  return 0;
}
### Prompt

Create a solution in Cpp for 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;
#define int long long
string s;
int n;
int used[300][300];
int dp[300][300];
int dfs(int p,int d){
  if(used[p][d]) return dp[p][d];
  used[p][d]=1;
  int res=-(1LL<<55LL),op=0;
  int j;
  for(j=p-1;j>=0;j--) if(s[j]=='+'||s[j]=='-') break;
  if(j>=0&&s[j]=='-') op=1;
  int x=((d+op)%2?-(s[p]-'0'):(s[p]-'0'));
  for(j=p+1;j<n;j++) if(isdigit(s[j])) break;
  if(j==n){
    //cout<<p<<" "<<d<<":"<<res<<"/"<<x<<endl;
    return dp[p][d]=x;
  }
  if(p<1||s[p-1]!='(') res=max(res,dfs(j,d)+x);
  if(p+1<n&&s[p+1]!=')') res=max(res,dfs(j,d+op)+x);
  if(d>0&&p-1>=0&&s[p-1]!='(') res=max(res,dfs(j,d-1)+x);
  //cout<<p<<" "<<d<<":"<<res<<"/"<<x<<endl;
  return dp[p][d]=res;
}
signed main(){
  cin>>s;
  n=s.length();
  int j;
  for(j=0;j<n;j++) if(isdigit(s[j])) break;
  cout<<dfs(j,0)<<endl;
  return 0;
}
```