#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

#define MIN first
#define MAX second
constexpr int MAX_S = 252;
constexpr int INF = (1 << 29);

string S;
pair<int, int> mem[MAX_S][MAX_S];

void init(int N)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            mem[i][j] = {+INF, -INF};
        }
    }
}

void update_max(int& l, int r)
{   
    if (l < r) l = r;
}

void update_min(int& l, int r)
{
    if (l > r) l = r;
}

// テ・ツ個コテゥツ鳴禿」ツ?ョpair(MIN, MAX)
pair<int, int> rec(int L, int R)
{
    pair<int, int>& res = mem[L][R];
    if (res != make_pair(+INF, -INF)) {
        return res;
    }

    if (R - L == 0) {
        int v = S[L] - '0';
        return (res = make_pair(v, v));
    }    

    if (S[L] == '(' && R - L > 2) {
        auto r = rec(L + 1, R);
        update_min(res.MIN, r.MIN);
        update_max(res.MAX, r.MAX);
        return res;
    }

    if (S[R] == ')' && R - L > 2) {
        auto r = rec(L, R - 1);
        update_min(res.MIN, r.MIN);
        update_max(res.MAX, r.MAX);
        return res;
    }
    
    for (int i = L + 1; i <= R - 1; i++) {
        char c = S[i];   
        if (c != '+' && c != '-') continue;                 
        
        auto res_l = rec(L, i - 1); // Left
        auto res_r = rec(i + 1, R); // Right

        if (c == '+') {            
            update_min(res.MIN, res_l.MIN + res_r.MIN);
            update_max(res.MAX, res_l.MAX + res_r.MAX);            
        }
        if (c == '-') {           
            update_min(res.MIN, res_l.MIN - res_r.MAX);
            update_max(res.MAX, res_l.MAX - res_r.MIN);
        }
    } 
    return res;
}

void solve()
{
    int N = S.size();
    init(N);
    cout << rec(0, N - 1).MAX << endl;    
}

int main()
{
    cin >> S;
    solve();    
    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 <cstring>
#include <algorithm>
#include <set>

using namespace std;

#define MIN first
#define MAX second
constexpr int MAX_S = 252;
constexpr int INF = (1 << 29);

string S;
pair<int, int> mem[MAX_S][MAX_S];

void init(int N)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            mem[i][j] = {+INF, -INF};
        }
    }
}

void update_max(int& l, int r)
{   
    if (l < r) l = r;
}

void update_min(int& l, int r)
{
    if (l > r) l = r;
}

// テ・ツ個コテゥツ鳴禿」ツ?ョpair(MIN, MAX)
pair<int, int> rec(int L, int R)
{
    pair<int, int>& res = mem[L][R];
    if (res != make_pair(+INF, -INF)) {
        return res;
    }

    if (R - L == 0) {
        int v = S[L] - '0';
        return (res = make_pair(v, v));
    }    

    if (S[L] == '(' && R - L > 2) {
        auto r = rec(L + 1, R);
        update_min(res.MIN, r.MIN);
        update_max(res.MAX, r.MAX);
        return res;
    }

    if (S[R] == ')' && R - L > 2) {
        auto r = rec(L, R - 1);
        update_min(res.MIN, r.MIN);
        update_max(res.MAX, r.MAX);
        return res;
    }
    
    for (int i = L + 1; i <= R - 1; i++) {
        char c = S[i];   
        if (c != '+' && c != '-') continue;                 
        
        auto res_l = rec(L, i - 1); // Left
        auto res_r = rec(i + 1, R); // Right

        if (c == '+') {            
            update_min(res.MIN, res_l.MIN + res_r.MIN);
            update_max(res.MAX, res_l.MAX + res_r.MAX);            
        }
        if (c == '-') {           
            update_min(res.MIN, res_l.MIN - res_r.MAX);
            update_max(res.MAX, res_l.MAX - res_r.MIN);
        }
    } 
    return res;
}

void solve()
{
    int N = S.size();
    init(N);
    cout << rec(0, N - 1).MAX << endl;    
}

int main()
{
    cin >> S;
    solve();    
    return 0;
}
```