#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 29;
const pair< int, int > wait = {INF, -INF};

string S;
pair< int, int > dp[200][200];

inline void merge(pair< int, int > &s, pair< int, int > t)
{
  s.first = min(s.first, t.first);
  s.second = max(s.second, t.second);
}


pair< int, int > rec(int l, int r)
{
  if(dp[l][r] != wait) return (dp[l][r]);
  if(l == r) return (dp[l][r] = make_pair(S[l] - '0', S[l] - '0'));
  if(S[l] == '(' && r - l > 2) merge(dp[l][r], rec(l + 1, r));
  if(S[r] == ')' && r - l > 2) merge(dp[l][r], rec(l, r - 1));
  for(int i = l + 1; i < r; i++) {
    if(S[i] != '+' && S[i] != '-') continue;
    auto p = rec(l, i - 1), q = rec(i + 1, r);
    if(S[i] == '+') merge(dp[l][r], {p.first + q.first, p.second + q.second});
    else merge(dp[l][r], {p.first - q.second, p.second - q.first});
  }
  return (dp[l][r]);
}

int main()
{
  fill_n(*dp, 200 * 200, wait);
  cin >> S;
  cout << rec(0, S.size() - 1).second << endl;
}
### 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<bits/stdc++.h>

using namespace std;

const int INF = 1 << 29;
const pair< int, int > wait = {INF, -INF};

string S;
pair< int, int > dp[200][200];

inline void merge(pair< int, int > &s, pair< int, int > t)
{
  s.first = min(s.first, t.first);
  s.second = max(s.second, t.second);
}


pair< int, int > rec(int l, int r)
{
  if(dp[l][r] != wait) return (dp[l][r]);
  if(l == r) return (dp[l][r] = make_pair(S[l] - '0', S[l] - '0'));
  if(S[l] == '(' && r - l > 2) merge(dp[l][r], rec(l + 1, r));
  if(S[r] == ')' && r - l > 2) merge(dp[l][r], rec(l, r - 1));
  for(int i = l + 1; i < r; i++) {
    if(S[i] != '+' && S[i] != '-') continue;
    auto p = rec(l, i - 1), q = rec(i + 1, r);
    if(S[i] == '+') merge(dp[l][r], {p.first + q.first, p.second + q.second});
    else merge(dp[l][r], {p.first - q.second, p.second - q.first});
  }
  return (dp[l][r]);
}

int main()
{
  fill_n(*dp, 200 * 200, wait);
  cin >> S;
  cout << rec(0, S.size() - 1).second << endl;
}
```