#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

PII dp[205][205];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  // [l,r]
  function<PII(int,int)> dfs = [&](int l, int r) -> PII {
    if(dp[l][r] != PII{-INF, INF}) return dp[l][r];
    if(l==r) return dp[l][r] = {s[l]-'0', s[l]-'0'};
    if(s[l]=='(' && r-l>=3) {
      PII p = dfs(l+1, r);
      chmax(dp[l][r].first, p.first);
      chmin(dp[l][r].second, p.second);
    }
    if(s[r]==')' && r-l>=3) {
      PII p = dfs(l, r-1);
      chmax(dp[l][r].first, p.first);
      chmin(dp[l][r].second, p.second);
    }
    FOR(i, l+1, r) {
      if(s[i]=='+' || s[i]=='-') {
        PII vl = dfs(l, i-1);
        PII vr = dfs(i+1, r);
        if(s[i]=='+') {
          chmax(dp[l][r].first, vl.first+vr.first);
          chmin(dp[l][r].second, vl.second+vr.second);
        } else {
          chmax(dp[l][r].first, vl.first-vr.second);
          chmin(dp[l][r].second, vl.second-vr.first);
        }
      }
    }
    return dp[l][r];
  };

  REP(i, s.size()) REP(j, s.size()) dp[i][j] = PII{-INF, INF};
  cout << dfs(0, s.size()-1).first << endl;

  // REP(i, s.size()) {
  //   FOR(j, i, s.size()) cout << dp[i][j] << " ";
  //   cout << endl;
  // }

  return 0;
}


### 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
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

PII dp[205][205];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  // [l,r]
  function<PII(int,int)> dfs = [&](int l, int r) -> PII {
    if(dp[l][r] != PII{-INF, INF}) return dp[l][r];
    if(l==r) return dp[l][r] = {s[l]-'0', s[l]-'0'};
    if(s[l]=='(' && r-l>=3) {
      PII p = dfs(l+1, r);
      chmax(dp[l][r].first, p.first);
      chmin(dp[l][r].second, p.second);
    }
    if(s[r]==')' && r-l>=3) {
      PII p = dfs(l, r-1);
      chmax(dp[l][r].first, p.first);
      chmin(dp[l][r].second, p.second);
    }
    FOR(i, l+1, r) {
      if(s[i]=='+' || s[i]=='-') {
        PII vl = dfs(l, i-1);
        PII vr = dfs(i+1, r);
        if(s[i]=='+') {
          chmax(dp[l][r].first, vl.first+vr.first);
          chmin(dp[l][r].second, vl.second+vr.second);
        } else {
          chmax(dp[l][r].first, vl.first-vr.second);
          chmin(dp[l][r].second, vl.second-vr.first);
        }
      }
    }
    return dp[l][r];
  };

  REP(i, s.size()) REP(j, s.size()) dp[i][j] = PII{-INF, INF};
  cout << dfs(0, s.size()-1).first << endl;

  // REP(i, s.size()) {
  //   FOR(j, i, s.size()) cout << dp[i][j] << " ";
  //   cout << endl;
  // }

  return 0;
}


```