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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int A[222],ope[222],bef[222],aft[222];


const int INF=1001001001001001001ll;
int mi[222][222];
int ma[222][222];

signed main(){
    string S;cin>>S;
    rep(i,S.size()){
        if(!isdigit(S[i]))continue;
        A[N]=S[i]-'0';
        if(i+1<S.size()&&S[i+1]==')')aft[N]=1;
        ope[N]=1;
        int t=i;
        while(t&&S[t-1]=='(')t--,bef[N]=1;
        if(t&&S[t-1]=='-')ope[N]=-1;
        N++;
    }

    fill_n(*ma,222*222,-INF);
    fill_n(*mi,222*222,INF);
    rep(i,N){
        if(!bef[i])mi[i][i+1]=ma[i][i+1]=A[i]*ope[i];
    }


    for(int len=2;len<=N;len++){
        for(int i=0;i+len<=N;i++){
            int j=i+len;
            for(int k=i+1;k<j;k++){
                chmax(ma[i][j],ma[i][k]+ma[k][j]);
                chmin(mi[i][j],mi[i][k]+mi[k][j]);
            }
            if(!aft[i]){
                if(ope[i]==1){
                    chmax(ma[i][j],A[i]+ma[i+1][j]);
                    chmin(mi[i][j],A[i]+mi[i+1][j]);
                }
                else{
                    chmax(ma[i][j],-A[i]-mi[i+1][j]);
                    chmin(mi[i][j],-A[i]-ma[i+1][j]);
                }
            }
        }
    }

    cout<<ma[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<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int A[222],ope[222],bef[222],aft[222];


const int INF=1001001001001001001ll;
int mi[222][222];
int ma[222][222];

signed main(){
    string S;cin>>S;
    rep(i,S.size()){
        if(!isdigit(S[i]))continue;
        A[N]=S[i]-'0';
        if(i+1<S.size()&&S[i+1]==')')aft[N]=1;
        ope[N]=1;
        int t=i;
        while(t&&S[t-1]=='(')t--,bef[N]=1;
        if(t&&S[t-1]=='-')ope[N]=-1;
        N++;
    }

    fill_n(*ma,222*222,-INF);
    fill_n(*mi,222*222,INF);
    rep(i,N){
        if(!bef[i])mi[i][i+1]=ma[i][i+1]=A[i]*ope[i];
    }


    for(int len=2;len<=N;len++){
        for(int i=0;i+len<=N;i++){
            int j=i+len;
            for(int k=i+1;k<j;k++){
                chmax(ma[i][j],ma[i][k]+ma[k][j]);
                chmin(mi[i][j],mi[i][k]+mi[k][j]);
            }
            if(!aft[i]){
                if(ope[i]==1){
                    chmax(ma[i][j],A[i]+ma[i+1][j]);
                    chmin(mi[i][j],A[i]+mi[i+1][j]);
                }
                else{
                    chmax(ma[i][j],-A[i]-mi[i+1][j]);
                    chmin(mi[i][j],-A[i]-ma[i+1][j]);
                }
            }
        }
    }

    cout<<ma[0][N]<<endl;
    return 0;
}
```