#include <iostream>
#include <cctype>
#include <vector>
using namespace std;

int main(){
    string S;
    cin>>S;
    vector<pair<int,int>> D;
    vector<char> OP;
    for(int i=0;i<S.size();i++){
        if(isdigit(S[i])) D.emplace_back(i,S[i]-'0');
        if(S[i]=='+'||S[i]=='-') OP.push_back(S[i]);

    }
    int N = D.size();
    bool R[N],L[N];
    fill(R,R+N,true);
    fill(L,L+N,true);
    R[0]=L[N-1]=false;
    for(int i=0;i<N;i++){
        if(D[i].first>0&&S[D[i].first-1]=='(') R[i]=false;
        if(D[i].first+1<S.size()&&S[D[i].first+1]==')') L[i]=false;
    }
    int DP_MIN[N][N+1],DP_MAX[N][N+1];//[l,r)
    fill(DP_MIN[0],DP_MIN[N],1000000);
    fill(DP_MAX[0],DP_MAX[N],-1000000);
    for(int i=0;i<N;i++){
        DP_MAX[i][i+1]=DP_MIN[i][i+1]=D[i].second;
    }
    for(int len=2;len<=N;len++){
        for(int l=0;l+len<=N;l++){
            if(L[l]&&R[l+len-1]){
                for(int r=l+1;r<l+len;r++){
                    if(DP_MAX[l][r]!=-1000000&&DP_MAX[r][l+len]!=-1000000){
                        DP_MAX[l][l+len]=max(DP_MAX[l][l+len],DP_MAX[l][r]+(OP[r-1]=='+'?DP_MAX[r][l+len]:-DP_MIN[r][l+len]));
                        DP_MIN[l][l+len]=min(DP_MIN[l][l+len],DP_MIN[l][r]+(OP[r-1]=='+'?DP_MIN[r][l+len]:-DP_MAX[r][l+len]));
                    }
                }
            }
            // cout<<"l: "<<l<<" r: "<<l+len<<' '<<DP_MIN[l][l+len]<<' '<<DP_MAX[l][l+len]<<endl;
        }
    }
    cout<<DP_MAX[0][N]<<endl;
    return 0;
}
### Prompt

Your challenge is to write a Cpp solution to 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 <iostream>
#include <cctype>
#include <vector>
using namespace std;

int main(){
    string S;
    cin>>S;
    vector<pair<int,int>> D;
    vector<char> OP;
    for(int i=0;i<S.size();i++){
        if(isdigit(S[i])) D.emplace_back(i,S[i]-'0');
        if(S[i]=='+'||S[i]=='-') OP.push_back(S[i]);

    }
    int N = D.size();
    bool R[N],L[N];
    fill(R,R+N,true);
    fill(L,L+N,true);
    R[0]=L[N-1]=false;
    for(int i=0;i<N;i++){
        if(D[i].first>0&&S[D[i].first-1]=='(') R[i]=false;
        if(D[i].first+1<S.size()&&S[D[i].first+1]==')') L[i]=false;
    }
    int DP_MIN[N][N+1],DP_MAX[N][N+1];//[l,r)
    fill(DP_MIN[0],DP_MIN[N],1000000);
    fill(DP_MAX[0],DP_MAX[N],-1000000);
    for(int i=0;i<N;i++){
        DP_MAX[i][i+1]=DP_MIN[i][i+1]=D[i].second;
    }
    for(int len=2;len<=N;len++){
        for(int l=0;l+len<=N;l++){
            if(L[l]&&R[l+len-1]){
                for(int r=l+1;r<l+len;r++){
                    if(DP_MAX[l][r]!=-1000000&&DP_MAX[r][l+len]!=-1000000){
                        DP_MAX[l][l+len]=max(DP_MAX[l][l+len],DP_MAX[l][r]+(OP[r-1]=='+'?DP_MAX[r][l+len]:-DP_MIN[r][l+len]));
                        DP_MIN[l][l+len]=min(DP_MIN[l][l+len],DP_MIN[l][r]+(OP[r-1]=='+'?DP_MIN[r][l+len]:-DP_MAX[r][l+len]));
                    }
                }
            }
            // cout<<"l: "<<l<<" r: "<<l+len<<' '<<DP_MIN[l][l+len]<<' '<<DP_MAX[l][l+len]<<endl;
        }
    }
    cout<<DP_MAX[0][N]<<endl;
    return 0;
}
```