#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

bool isvalid(int b, int e, vector<int> &num, string &str){
    if(b==e || (str[num[b]+1]!=')' && str[num[e]-1]!='(')){
        return true;
    }
    return false;
}

int main(){
    string str;
    cin >> str;
    vector<int> num, op;
    for(int i=0; i<(int)str.length(); i++){
        if('0'<=str[i] && str[i]<='9') num.push_back(i);
        if(str[i]=='+' || str[i]=='-') op.push_back(i);
    }
    
    int n = num.size();
    vector<vector<int> > dpmin(n, vector<int>(n, inf)), dpmax(n, vector<int>(n, -inf));;
    for(int i=0; i<n; i++) dpmin[i][i] = dpmax[i][i] = str[num[i]]-'0';
    
    for(int j=1; j<n; j++){
        for(int i=0; i+j<n; i++){
            for(int k=0; k<j; k++){
                if(isvalid(i, i+k, num, str) && isvalid(i+k+1, i+j, num, str)){
                    if(str[op[i+k]] == '+'){
                        dpmax[i][i+j] = max(dpmax[i][i+j], dpmax[i][i+k]+dpmax[i+k+1][i+j]);
                        dpmin[i][i+j] = min(dpmin[i][i+j], dpmin[i][i+k]+dpmin[i+k+1][i+j]);
                    }else{
                        dpmax[i][i+j] = max(dpmax[i][i+j], dpmax[i][i+k]-dpmin[i+k+1][i+j]);
                        dpmin[i][i+j] = min(dpmin[i][i+j], dpmin[i][i+k]-dpmax[i+k+1][i+j]);
                    }
                }
            }
        }
    }
    cout << dpmax[0][n-1] << endl;
    return 0;
}


### Prompt

Generate 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 <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

bool isvalid(int b, int e, vector<int> &num, string &str){
    if(b==e || (str[num[b]+1]!=')' && str[num[e]-1]!='(')){
        return true;
    }
    return false;
}

int main(){
    string str;
    cin >> str;
    vector<int> num, op;
    for(int i=0; i<(int)str.length(); i++){
        if('0'<=str[i] && str[i]<='9') num.push_back(i);
        if(str[i]=='+' || str[i]=='-') op.push_back(i);
    }
    
    int n = num.size();
    vector<vector<int> > dpmin(n, vector<int>(n, inf)), dpmax(n, vector<int>(n, -inf));;
    for(int i=0; i<n; i++) dpmin[i][i] = dpmax[i][i] = str[num[i]]-'0';
    
    for(int j=1; j<n; j++){
        for(int i=0; i+j<n; i++){
            for(int k=0; k<j; k++){
                if(isvalid(i, i+k, num, str) && isvalid(i+k+1, i+j, num, str)){
                    if(str[op[i+k]] == '+'){
                        dpmax[i][i+j] = max(dpmax[i][i+j], dpmax[i][i+k]+dpmax[i+k+1][i+j]);
                        dpmin[i][i+j] = min(dpmin[i][i+j], dpmin[i][i+k]+dpmin[i+k+1][i+j]);
                    }else{
                        dpmax[i][i+j] = max(dpmax[i][i+j], dpmax[i][i+k]-dpmin[i+k+1][i+j]);
                        dpmin[i][i+j] = min(dpmin[i][i+j], dpmin[i][i+k]-dpmax[i+k+1][i+j]);
                    }
                }
            }
        }
    }
    cout << dpmax[0][n-1] << endl;
    return 0;
}


```