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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(a) (a).begin(),(a).end()

constexpr int INF = 1000000000;

enum CYK_TABLE {
  DIGIT,
  LPAR,
  RPAR,
  PLUS,
  MINUS,
  TERM,
  RPEXPR,
  RMEXPR,
  LEXPR,
  EXPR
};

int main(){
  int N = 10;
  string s;
  cin>>s;
  int n = s.size();
  vector<vector<vector<bool>>> cyk(n, vector<vector<bool>>(n+1, vector<bool>(N, false)));
  vector<vector<vector<int>>> mn(n, vector<vector<int>>(n+1, vector<int>(N, INF)));
  vector<vector<vector<int>>> mx(n, vector<vector<int>>(n+1, vector<int>(N, -INF)));
  REP(i,n) {
    if (isdigit(s[i])) {
      cyk[i][1][DIGIT] = true;
      mn[i][1][DIGIT] = s[i] - '0';
      mx[i][1][DIGIT] = s[i] - '0';
    } else {
      switch (s[i]) {
        case '(':
        cyk[i][1][LPAR] = true;
        break;
        case ')':
        cyk[i][1][RPAR] = true;
        break;
        case '+':
        cyk[i][1][PLUS] = true;
        break;
        case '-':
        cyk[i][1][MINUS] = true;
        break;
      }
    }
  }
  vector<pair<int, int>> m = {
    {DIGIT, TERM},
    {EXPR, TERM},
    {EXPR, LEXPR},
    {LEXPR, EXPR}
  };
  map<pair<int,int>, int> m2 = {
    {{PLUS, TERM}, RPEXPR},
    {{TERM, RPEXPR}, EXPR},
    {{MINUS, TERM}, RMEXPR},
    {{TERM, RMEXPR}, EXPR},
    {{LPAR, EXPR}, LEXPR},
    {{LEXPR, RPAR}, EXPR}
  };
  for (int l = 1; l <= n; ++l) {
    REP(i,n) {
      if (i+l > n) continue;
      REP(k,l) {
        if (k == 0) continue;
        for (auto p : m2) {
          int left, right, res;
          pair<int,int> tmp;
          tie(tmp, res) = p;
          tie(left, right) = tmp;
          if (cyk[i][k][left] && cyk[i+k][l-k][right]) {
            cyk[i][l][res] = true;
            if (right == RPEXPR) {
              mn[i][l][res] = min(mn[i][l][res],
                  mn[i][k][left] + mn[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res],
                  mx[i][k][left] + mx[i+k][l-k][right]);
            } else if (right == RMEXPR) {
              mn[i][l][res] = min(mn[i][l][res],
                  mn[i][k][left] - mx[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res],
                  mx[i][k][left] - mn[i+k][l-k][right]);
            } else if (right == EXPR || right == TERM) {
              mn[i][l][res] = min(mn[i][l][res], mn[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res], mx[i+k][l-k][right]);
            } else if (left == LEXPR) {
              mn[i][l][res] = min(mn[i][l][res], mn[i][k][left]);
              mx[i][l][res] = max(mx[i][l][res], mx[i][k][left]);
            }
          }
        }
      }
      while (true) {
      bool update = false;
        for (auto p : m) {
          int src, res;
          tie(src, res) = p;
          if (cyk[i][l][src]) {
            if (!cyk[i][l][res]) update = true;
            cyk[i][l][res] = true;
            mn[i][l][res] = min(mn[i][l][res], mn[i][l][src]);
            mx[i][l][res] = max(mx[i][l][res], mx[i][l][src]);
          }
        }
        if (!update) break;
      }
    }
  }
  cout << mx[0][n][EXPR] << endl;
  return 0;
}
### Prompt

In Cpp, your task is to solve 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>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(a) (a).begin(),(a).end()

constexpr int INF = 1000000000;

enum CYK_TABLE {
  DIGIT,
  LPAR,
  RPAR,
  PLUS,
  MINUS,
  TERM,
  RPEXPR,
  RMEXPR,
  LEXPR,
  EXPR
};

int main(){
  int N = 10;
  string s;
  cin>>s;
  int n = s.size();
  vector<vector<vector<bool>>> cyk(n, vector<vector<bool>>(n+1, vector<bool>(N, false)));
  vector<vector<vector<int>>> mn(n, vector<vector<int>>(n+1, vector<int>(N, INF)));
  vector<vector<vector<int>>> mx(n, vector<vector<int>>(n+1, vector<int>(N, -INF)));
  REP(i,n) {
    if (isdigit(s[i])) {
      cyk[i][1][DIGIT] = true;
      mn[i][1][DIGIT] = s[i] - '0';
      mx[i][1][DIGIT] = s[i] - '0';
    } else {
      switch (s[i]) {
        case '(':
        cyk[i][1][LPAR] = true;
        break;
        case ')':
        cyk[i][1][RPAR] = true;
        break;
        case '+':
        cyk[i][1][PLUS] = true;
        break;
        case '-':
        cyk[i][1][MINUS] = true;
        break;
      }
    }
  }
  vector<pair<int, int>> m = {
    {DIGIT, TERM},
    {EXPR, TERM},
    {EXPR, LEXPR},
    {LEXPR, EXPR}
  };
  map<pair<int,int>, int> m2 = {
    {{PLUS, TERM}, RPEXPR},
    {{TERM, RPEXPR}, EXPR},
    {{MINUS, TERM}, RMEXPR},
    {{TERM, RMEXPR}, EXPR},
    {{LPAR, EXPR}, LEXPR},
    {{LEXPR, RPAR}, EXPR}
  };
  for (int l = 1; l <= n; ++l) {
    REP(i,n) {
      if (i+l > n) continue;
      REP(k,l) {
        if (k == 0) continue;
        for (auto p : m2) {
          int left, right, res;
          pair<int,int> tmp;
          tie(tmp, res) = p;
          tie(left, right) = tmp;
          if (cyk[i][k][left] && cyk[i+k][l-k][right]) {
            cyk[i][l][res] = true;
            if (right == RPEXPR) {
              mn[i][l][res] = min(mn[i][l][res],
                  mn[i][k][left] + mn[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res],
                  mx[i][k][left] + mx[i+k][l-k][right]);
            } else if (right == RMEXPR) {
              mn[i][l][res] = min(mn[i][l][res],
                  mn[i][k][left] - mx[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res],
                  mx[i][k][left] - mn[i+k][l-k][right]);
            } else if (right == EXPR || right == TERM) {
              mn[i][l][res] = min(mn[i][l][res], mn[i+k][l-k][right]);
              mx[i][l][res] = max(mx[i][l][res], mx[i+k][l-k][right]);
            } else if (left == LEXPR) {
              mn[i][l][res] = min(mn[i][l][res], mn[i][k][left]);
              mx[i][l][res] = max(mx[i][l][res], mx[i][k][left]);
            }
          }
        }
      }
      while (true) {
      bool update = false;
        for (auto p : m) {
          int src, res;
          tie(src, res) = p;
          if (cyk[i][l][src]) {
            if (!cyk[i][l][res]) update = true;
            cyk[i][l][res] = true;
            mn[i][l][res] = min(mn[i][l][res], mn[i][l][src]);
            mx[i][l][res] = max(mx[i][l][res], mx[i][l][src]);
          }
        }
        if (!update) break;
      }
    }
  }
  cout << mx[0][n][EXPR] << endl;
  return 0;
}
```