#include "bits/stdc++.h"
using namespace std;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710&lang=jp
// reference : http://suikaba.hatenablog.com/entry/2017/05/24/231631
typedef pair<int, int> pii;
#define INF 1<<25

pii rec(int l, int r, const string& S,vector<vector<pii>>& dp) {
	pii& ret = dp[l][r];
	/* Updated */
	if (ret != pii{ -INF, INF }) return ret;

	if (l == r) {
		return ret = { S[l] - '0',S[l] - '0' };
	}

	if (S[l] == '(' && r - l >= 3) {
		pii x = rec(l + 1, r, S, dp);
		ret.first = max(ret.first, x.first);
		ret.second = min(ret.second, x.second);
	}
	if (S[r] == ')' && r - l >= 3) {
		pii x = rec(l, r - 1, S, dp);
		ret.first = max(ret.first, x.first);
		ret.second = min(ret.second, x.second);
	}
	for (int m = l + 1; m < r; m++) {
		if (S[m] == '+' || S[m] == '-') {
			pii x1 = rec(l, m - 1, S, dp);
			pii x2 = rec(m + 1, r, S, dp);
			if (S[m] == '+') {
				ret.first = max(ret.first, x1.first + x2.first);
				ret.second = min(ret.second, x1.second + x2.second);
			}
			else {
				ret.first = max(ret.first, x1.first - x2.second);
				ret.second = min(ret.second, x1.second - x2.first);
			}
		}
	}
	return ret;
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	string S; cin >> S;
	/*  dp[l][r] := { maximum value of the interval(l-r) , minimum value of ~ }*/
	vector<vector<pii>> dp(S.length(), vector<pii>(S.length(), { -INF,INF }));
	cout << rec(0, S.length() - 1, S, dp).first << endl;
}
### Prompt

Please formulate 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;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2710&lang=jp
// reference : http://suikaba.hatenablog.com/entry/2017/05/24/231631
typedef pair<int, int> pii;
#define INF 1<<25

pii rec(int l, int r, const string& S,vector<vector<pii>>& dp) {
	pii& ret = dp[l][r];
	/* Updated */
	if (ret != pii{ -INF, INF }) return ret;

	if (l == r) {
		return ret = { S[l] - '0',S[l] - '0' };
	}

	if (S[l] == '(' && r - l >= 3) {
		pii x = rec(l + 1, r, S, dp);
		ret.first = max(ret.first, x.first);
		ret.second = min(ret.second, x.second);
	}
	if (S[r] == ')' && r - l >= 3) {
		pii x = rec(l, r - 1, S, dp);
		ret.first = max(ret.first, x.first);
		ret.second = min(ret.second, x.second);
	}
	for (int m = l + 1; m < r; m++) {
		if (S[m] == '+' || S[m] == '-') {
			pii x1 = rec(l, m - 1, S, dp);
			pii x2 = rec(m + 1, r, S, dp);
			if (S[m] == '+') {
				ret.first = max(ret.first, x1.first + x2.first);
				ret.second = min(ret.second, x1.second + x2.second);
			}
			else {
				ret.first = max(ret.first, x1.first - x2.second);
				ret.second = min(ret.second, x1.second - x2.first);
			}
		}
	}
	return ret;
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	string S; cin >> S;
	/*  dp[l][r] := { maximum value of the interval(l-r) , minimum value of ~ }*/
	vector<vector<pii>> dp(S.length(), vector<pii>(S.length(), { -INF,INF }));
	cout << rec(0, S.length() - 1, S, dp).first << endl;
}
```