#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mod  1000000007
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);i++)
    

int mx[210][210];
bool mxflag[210][210];
int mi[210][210];
bool miflag[210][210];
int n;
string s;

int mxdfs(int l,int r);
int midfs(int l,int r);

int mxdfs(int l,int r){
    if(s[l]=='('||s[r]==')'){
        int c = 0;
        for(int i=l;i<=r;i++){
            if(isdigit(s[i]))c++;
        }
        if(c==1){
            return -inf;
        }
    }
    if(s[l]=='(')return mxdfs(l+1,r); 
    if(s[r]==')')return mxdfs(l,r-1);
    if(mxflag[l][r])return mx[l][r];
    if(l==r){
        return s[l]-'0';
    }
    if(s[r-1]=='(')return -inf;
    int res = -inf;
    for(int i=l;i<=r;i++){
        if(s[i]=='-'){
            res = max(mxdfs(l,i-1)-midfs(i+1,r),res);
        }else if(s[i]=='+'){
            res = max(mxdfs(l,i-1)+mxdfs(i+1,r),res);
        
        }
    }
    mxflag[l][r] = 1;
    return mx[l][r] = res;
}
int midfs(int l,int r){
    if(s[l]=='('||s[r]==')'){
        int c = 0;
        for(int i=l;i<=r;i++){
            if(isdigit(s[i]))c++;
        }
        if(c==1){
            return inf;
        }
    }
    if(s[l]=='(')return midfs(l+1,r); 
    if(s[r]==')')return midfs(l,r-1);
    if(miflag[l][r])return mi[l][r];
    if(l==r){
        return s[l]-'0';
    }
    if(s[l+1]==')')return inf;
    int res = inf;
    for(int i=l;i<=r;i++){
        if(s[i]=='-'){
            res = min(midfs(l,i-1)-mxdfs(i+1,r),res);
        }else if(s[i]=='+'){
            res = min(midfs(l,i-1)+midfs(i+1,r),res);
        
        }
    }
    miflag[l][r] = 1;
    return mi[l][r] = res;
}


int main(){
    cin >> s;
    n = s.size();
    cout << mxdfs(0,n-1) << 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<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mod  1000000007
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);i++)
    

int mx[210][210];
bool mxflag[210][210];
int mi[210][210];
bool miflag[210][210];
int n;
string s;

int mxdfs(int l,int r);
int midfs(int l,int r);

int mxdfs(int l,int r){
    if(s[l]=='('||s[r]==')'){
        int c = 0;
        for(int i=l;i<=r;i++){
            if(isdigit(s[i]))c++;
        }
        if(c==1){
            return -inf;
        }
    }
    if(s[l]=='(')return mxdfs(l+1,r); 
    if(s[r]==')')return mxdfs(l,r-1);
    if(mxflag[l][r])return mx[l][r];
    if(l==r){
        return s[l]-'0';
    }
    if(s[r-1]=='(')return -inf;
    int res = -inf;
    for(int i=l;i<=r;i++){
        if(s[i]=='-'){
            res = max(mxdfs(l,i-1)-midfs(i+1,r),res);
        }else if(s[i]=='+'){
            res = max(mxdfs(l,i-1)+mxdfs(i+1,r),res);
        
        }
    }
    mxflag[l][r] = 1;
    return mx[l][r] = res;
}
int midfs(int l,int r){
    if(s[l]=='('||s[r]==')'){
        int c = 0;
        for(int i=l;i<=r;i++){
            if(isdigit(s[i]))c++;
        }
        if(c==1){
            return inf;
        }
    }
    if(s[l]=='(')return midfs(l+1,r); 
    if(s[r]==')')return midfs(l,r-1);
    if(miflag[l][r])return mi[l][r];
    if(l==r){
        return s[l]-'0';
    }
    if(s[l+1]==')')return inf;
    int res = inf;
    for(int i=l;i<=r;i++){
        if(s[i]=='-'){
            res = min(midfs(l,i-1)-mxdfs(i+1,r),res);
        }else if(s[i]=='+'){
            res = min(midfs(l,i-1)+midfs(i+1,r),res);
        
        }
    }
    miflag[l][r] = 1;
    return mi[l][r] = res;
}


int main(){
    cin >> s;
    n = s.size();
    cout << mxdfs(0,n-1) << endl;
    
    
    return 0;
}

```