#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll INF=1e9;
void cmax(ll &lhs,ll rhs){
    lhs=max(lhs,rhs);
}
void cmin(ll &lhs,ll rhs){
    lhs=min(lhs,rhs);
}
int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<vector<ll>> dpmax(n,vector<ll>(n+1,-INF));
    vector<vector<ll>> dpmin(n,vector<ll>(n+1,INF));
    for(int k=1;k<=n;k++){
        for(int l=0;l+k<=n;l++){
            int r=l+k;
            if(k==1){
                if(isdigit(s[l])){
                    dpmax[l][r]=s[l]-'0';
                    dpmin[l][r]=s[l]-'0';
                }
            }
            else if(s[l]=='(' || s[r-1]==')'){
                int cnt=0;
                for(int i=l;i<r;i++){
                    cnt+=(int)(isdigit(s[i]));
                }
                if(cnt>=2){
                    if(s[l]=='('){
                        dpmax[l][r]=dpmax[l+1][r];
                        dpmin[l][r]=dpmin[l+1][r];
                    }
                    else{
                        dpmax[l][r]=dpmax[l][r-1];
                        dpmin[l][r]=dpmin[l][r-1];
                    }
                }
            }
            else{
                for(int i=l;i<r;i++){
                    if(s[i]=='+'){
                        cmax(dpmax[l][r],dpmax[l][i]+dpmax[i+1][r]);
                        cmin(dpmin[l][r],dpmin[l][i]+dpmin[i+1][r]);
                    }
                    if(s[i]=='-'){
                        cmax(dpmax[l][r],dpmax[l][i]-dpmin[i+1][r]);
                        cmin(dpmin[l][r],dpmin[l][i]-dpmax[i+1][r]);
                    }
                }

            }
        }
    }
    cout<<dpmax[0][n]<<endl;

    return 0;
}

### Prompt

Please formulate 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<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll INF=1e9;
void cmax(ll &lhs,ll rhs){
    lhs=max(lhs,rhs);
}
void cmin(ll &lhs,ll rhs){
    lhs=min(lhs,rhs);
}
int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<vector<ll>> dpmax(n,vector<ll>(n+1,-INF));
    vector<vector<ll>> dpmin(n,vector<ll>(n+1,INF));
    for(int k=1;k<=n;k++){
        for(int l=0;l+k<=n;l++){
            int r=l+k;
            if(k==1){
                if(isdigit(s[l])){
                    dpmax[l][r]=s[l]-'0';
                    dpmin[l][r]=s[l]-'0';
                }
            }
            else if(s[l]=='(' || s[r-1]==')'){
                int cnt=0;
                for(int i=l;i<r;i++){
                    cnt+=(int)(isdigit(s[i]));
                }
                if(cnt>=2){
                    if(s[l]=='('){
                        dpmax[l][r]=dpmax[l+1][r];
                        dpmin[l][r]=dpmin[l+1][r];
                    }
                    else{
                        dpmax[l][r]=dpmax[l][r-1];
                        dpmin[l][r]=dpmin[l][r-1];
                    }
                }
            }
            else{
                for(int i=l;i<r;i++){
                    if(s[i]=='+'){
                        cmax(dpmax[l][r],dpmax[l][i]+dpmax[i+1][r]);
                        cmin(dpmin[l][r],dpmin[l][i]+dpmin[i+1][r]);
                    }
                    if(s[i]=='-'){
                        cmax(dpmax[l][r],dpmax[l][i]-dpmin[i+1][r]);
                        cmin(dpmin[l][r],dpmin[l][i]-dpmax[i+1][r]);
                    }
                }

            }
        }
    }
    cout<<dpmax[0][n]<<endl;

    return 0;
}

```