#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
inline void chmax(int &a, const int &b) {a = max(a, b);}
inline void chmin(int &a, const int &b) {a = min(a, b);}
const int INF = 1 << 28;
string s;
int N;
pii dp[210][210], INIT;

pii solve(int l, int r) {
    pii &res = dp[l][r];
    if(dp[l][r] != INIT) return res;
    // 数字
    if(r - l == 1) {
        int val = s[l] - '0';
        return res = make_pair(val, val);
    }
    // 括弧をとっぱらって再帰的に
    // このとき、括弧含め幅が 3 以下 (つまり実質 2 以下) だと
    // 数式になりえないので飛ばす
    if(s[l] == '(' && r-l > 3) {
        pii tmp = solve(l+1, r);
        res.first = max(res.first, tmp.first);
        res.second = min(res.second, tmp.second);
    }
    if(s[r-1] == ')' && r-l > 3) {
        pii tmp = solve(l, r-1);
        res.first = max(res.first, tmp.first);
        res.second = min(res.second, tmp.second);
    }
    for(int k=l; k<r; k++) {
        if(s[k] != '+' && s[k] != '-') continue;
        pii v1 = solve(l, k), v2 = solve(k+1, r);
        if(s[k] == '+') {
            res.first = max(res.first, v1.first + v2.first);
            res.second = min(res.second, v1.second + v2.second);
        }
        else {
            res.first = max(res.first, v1.first - v2.second);
            res.second = min(res.second, v1.second - v2.first);
        }
    }
    return res;
}

int main() {
    cin >> s;
    N = s.length();
    INIT = make_pair(-INF, INF);
    for(int i=0; i<N; i++) {
        fill(dp[i], dp[i] + N + 1, INIT);
    }

    cout << solve(0, N).first << endl;
    /*
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<=N; j++) {
            if(dp_max[i][j] == -INF) continue;
            printf("%s\n", s.c_str());
            for(int k=0; k<N; k++) {
                if(i <= k && k < j) printf("=");
                else printf(" ");
            }
            printf(" -> %d\n", dp_max[i][j]);
        }
    }
    */
    return 0;
}

### Prompt

Create a solution in CPP for 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 <cstdio>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
inline void chmax(int &a, const int &b) {a = max(a, b);}
inline void chmin(int &a, const int &b) {a = min(a, b);}
const int INF = 1 << 28;
string s;
int N;
pii dp[210][210], INIT;

pii solve(int l, int r) {
    pii &res = dp[l][r];
    if(dp[l][r] != INIT) return res;
    // 数字
    if(r - l == 1) {
        int val = s[l] - '0';
        return res = make_pair(val, val);
    }
    // 括弧をとっぱらって再帰的に
    // このとき、括弧含め幅が 3 以下 (つまり実質 2 以下) だと
    // 数式になりえないので飛ばす
    if(s[l] == '(' && r-l > 3) {
        pii tmp = solve(l+1, r);
        res.first = max(res.first, tmp.first);
        res.second = min(res.second, tmp.second);
    }
    if(s[r-1] == ')' && r-l > 3) {
        pii tmp = solve(l, r-1);
        res.first = max(res.first, tmp.first);
        res.second = min(res.second, tmp.second);
    }
    for(int k=l; k<r; k++) {
        if(s[k] != '+' && s[k] != '-') continue;
        pii v1 = solve(l, k), v2 = solve(k+1, r);
        if(s[k] == '+') {
            res.first = max(res.first, v1.first + v2.first);
            res.second = min(res.second, v1.second + v2.second);
        }
        else {
            res.first = max(res.first, v1.first - v2.second);
            res.second = min(res.second, v1.second - v2.first);
        }
    }
    return res;
}

int main() {
    cin >> s;
    N = s.length();
    INIT = make_pair(-INF, INF);
    for(int i=0; i<N; i++) {
        fill(dp[i], dp[i] + N + 1, INIT);
    }

    cout << solve(0, N).first << endl;
    /*
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<=N; j++) {
            if(dp_max[i][j] == -INF) continue;
            printf("%s\n", s.c_str());
            for(int k=0; k<N; k++) {
                if(i <= k && k < j) printf("=");
                else printf(" ");
            }
            printf(" -> %d\n", dp_max[i][j]);
        }
    }
    */
    return 0;
}

```