#include <bits/stdc++.h>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;

const int inf = 1 << 24;

int main(void){
    string s; cin >> s;

    vi num, br_l, br_r;
    string op;
    rep(i, (int)s.size()){
        if(isdigit(s[i])){
            num.pb(s[i] - '0');
            if(0 <= i - 1 && s[i - 1] == '(')            br_l.pb(true);
            else                                         br_l.pb(false);
            if(i + 1 < (int)s.size() && s[i + 1] == ')') br_r.pb(true);
            else                                         br_r.pb(false);
        }
        if(s[i] == '+' || s[i] == '-'){
            op.pb(s[i]);
        }
    }

    vvi dp_max(num.size(), vi(num.size(), -inf));
    vvi dp_min(num.size(), vi(num.size(), inf));
    rep(i, (int)num.size()){
        dp_max[i][i] = dp_min[i][i] = num[i];
    }

    range(i, 2, (int)num.size() + 1){    // len 
        rep(j, (int)num.size() - i + 1){ // l such [l, l + len)
            int l = j, r = j + i - 1;
            if(br_r[l] || br_l[r]) continue;

            range(k, l + 1, r + 1){
                //if(br_l[k - 1] || br_r[k]) continue;
                
                if(op[k - 1] == '+'){
                    if(dp_min[l][k - 1] != inf && dp_min[k][r] != inf)
                        dp_min[l][r] = min(dp_min[l][r], dp_min[l][k - 1] + dp_min[k][r]);
                    if(dp_max[l][k - 1] != -inf && dp_max[k][r] != -inf)
                        dp_max[l][r] = max(dp_max[l][r], dp_max[l][k - 1] + dp_max[k][r]);
                }
                else {
                    if(dp_min[l][k - 1] != inf && dp_max[k][r] != -inf)
                        dp_min[l][r] = min(dp_min[l][r], dp_min[l][k - 1] - dp_max[k][r]);
                    if(dp_max[l][k - 1] != -inf && dp_min[k][r] != inf)
                        dp_max[l][r] = max(dp_max[l][r], dp_max[l][k - 1] - dp_min[k][r]);
                }
            }
        }
    }

    cout << dp_max[0][(int)num.size() - 1] << 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>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;

#define pb push_back
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;

const int inf = 1 << 24;

int main(void){
    string s; cin >> s;

    vi num, br_l, br_r;
    string op;
    rep(i, (int)s.size()){
        if(isdigit(s[i])){
            num.pb(s[i] - '0');
            if(0 <= i - 1 && s[i - 1] == '(')            br_l.pb(true);
            else                                         br_l.pb(false);
            if(i + 1 < (int)s.size() && s[i + 1] == ')') br_r.pb(true);
            else                                         br_r.pb(false);
        }
        if(s[i] == '+' || s[i] == '-'){
            op.pb(s[i]);
        }
    }

    vvi dp_max(num.size(), vi(num.size(), -inf));
    vvi dp_min(num.size(), vi(num.size(), inf));
    rep(i, (int)num.size()){
        dp_max[i][i] = dp_min[i][i] = num[i];
    }

    range(i, 2, (int)num.size() + 1){    // len 
        rep(j, (int)num.size() - i + 1){ // l such [l, l + len)
            int l = j, r = j + i - 1;
            if(br_r[l] || br_l[r]) continue;

            range(k, l + 1, r + 1){
                //if(br_l[k - 1] || br_r[k]) continue;
                
                if(op[k - 1] == '+'){
                    if(dp_min[l][k - 1] != inf && dp_min[k][r] != inf)
                        dp_min[l][r] = min(dp_min[l][r], dp_min[l][k - 1] + dp_min[k][r]);
                    if(dp_max[l][k - 1] != -inf && dp_max[k][r] != -inf)
                        dp_max[l][r] = max(dp_max[l][r], dp_max[l][k - 1] + dp_max[k][r]);
                }
                else {
                    if(dp_min[l][k - 1] != inf && dp_max[k][r] != -inf)
                        dp_min[l][r] = min(dp_min[l][r], dp_min[l][k - 1] - dp_max[k][r]);
                    if(dp_max[l][k - 1] != -inf && dp_min[k][r] != inf)
                        dp_max[l][r] = max(dp_max[l][r], dp_max[l][k - 1] - dp_min[k][r]);
                }
            }
        }
    }

    cout << dp_max[0][(int)num.size() - 1] << endl;

    return 0;
}
```