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

using P = pair<int, int>;

constexpr int INF = 1e9;

P memo[201][201];

P rec(int l, int r, string const& s) {
    P& res = memo[l][r];
    if(res != P{-INF, INF}) {
        return res;
    }
    if(l == r) {
        int v = s[l] - '0';
        return res = make_pair(v, v);
    }
    if(s[l] == '(' && r-l >= 3) {
        P p = rec(l+1, r, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    if(s[r] == ')' && r-l >= 3) {
        P p = rec(l, r-1, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    for(int i=l+1; i<r; ++i) {
        char op = s[i];
        if(op == '+' || op == '-') {
            P rl = rec(l, i-1, s);
            P rr = rec(i+1, r, s);
            if(op == '+') {
                res.first = max(res.first, rl.first + rr.first);
                res.second = min(res.second, rl.second + rr.second);
            } else {
                res.first = max(res.first, rl.first - rr.second);
                res.second = min(res.second, rl.second - rr.first);
            }
        }
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); ++i) {
        for(int j=0; j<s.size(); ++j) {
            memo[i][j] = make_pair(-INF, INF);
        }
    }
    cout << rec(0, s.size()-1, s).first << endl;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 P = pair<int, int>;

constexpr int INF = 1e9;

P memo[201][201];

P rec(int l, int r, string const& s) {
    P& res = memo[l][r];
    if(res != P{-INF, INF}) {
        return res;
    }
    if(l == r) {
        int v = s[l] - '0';
        return res = make_pair(v, v);
    }
    if(s[l] == '(' && r-l >= 3) {
        P p = rec(l+1, r, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    if(s[r] == ')' && r-l >= 3) {
        P p = rec(l, r-1, s);
        res.first = max(res.first, p.first);
        res.second = min(res.second, p.second);
    }
    for(int i=l+1; i<r; ++i) {
        char op = s[i];
        if(op == '+' || op == '-') {
            P rl = rec(l, i-1, s);
            P rr = rec(i+1, r, s);
            if(op == '+') {
                res.first = max(res.first, rl.first + rr.first);
                res.second = min(res.second, rl.second + rr.second);
            } else {
                res.first = max(res.first, rl.first - rr.second);
                res.second = min(res.second, rl.second - rr.first);
            }
        }
    }
    return res;
}

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); ++i) {
        for(int j=0; j<s.size(); ++j) {
            memo[i][j] = make_pair(-INF, INF);
        }
    }
    cout << rec(0, s.size()-1, s).first << endl;
}

```