#include <bits/stdc++.h>

using i2 = std::array<int64_t, 2>;

std::string S;

i2 calcFormula(int& s_i);

int main()
{
	std::cin >> S;
	int s_i{};
	printf("%lld\n", calcFormula(s_i)[1]);

	return 0;
}

i2 calcFormula(int& s_i)
{
	std::vector<int> num;
	std::vector<bool> isBegin(1), isEnd(1);
	while (S[s_i] == '(')
	{
		s_i++;
		isBegin.back() = true;
	}
	num.push_back(S[s_i] - '0');
	s_i++;
	while (S[s_i] == ')')
	{
		s_i++;
		isEnd.back() = true;
	}
	std::vector<char> operators;
	while (s_i < (int)S.size())
	{
		operators.push_back(S[s_i]);
		s_i++;
		isBegin.push_back(false);
		while (S[s_i] == '(')
		{
			isBegin.back() = true;
			s_i++;
		}
		num.push_back(S[s_i] - '0');
		s_i++;
		isEnd.push_back(false);
		while (s_i < (int)S.size() && S[s_i] == ')')
		{
			isEnd.back() = true;
			s_i++;
		}
	}
	using vi = std::vector<int64_t>;
	using vvi = std::vector<vi>;
	int size{(int)num.size()};
	vvi minTable(size + 1, vi(size + 1, 1ll << 60)), maxTable(size + 1, vi(size + 1, -(1ll << 60)));
	for (int i{}; i < size; i++)
		minTable[i][i + 1] = maxTable[i][i + 1] = num[i];
	for (int width{2}; width <= size; width++)
		for (int left{}; left + width <= size; left++)
		{
			int right{left + width};
			if (isEnd[left] || isBegin[right - 1]) continue;
			for (int mid{left + 1}; mid < right; mid++)
			{
				if (operators[mid - 1] == '+')
				{
					minTable[left][right] = std::min(minTable[left][right], minTable[left][mid] + minTable[mid][right]);
					maxTable[left][right] = std::max(maxTable[left][right], maxTable[left][mid] + maxTable[mid][right]);
				}
				else
				{
					minTable[left][right] = std::min(minTable[left][right], minTable[left][mid] - maxTable[mid][right]);
					maxTable[left][right] = std::max(maxTable[left][right], maxTable[left][mid] - minTable[mid][right]);
				}
			}
		}
	return {minTable[0][size], maxTable[0][size]};
}

### Prompt

Please create a solution in CPP 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 i2 = std::array<int64_t, 2>;

std::string S;

i2 calcFormula(int& s_i);

int main()
{
	std::cin >> S;
	int s_i{};
	printf("%lld\n", calcFormula(s_i)[1]);

	return 0;
}

i2 calcFormula(int& s_i)
{
	std::vector<int> num;
	std::vector<bool> isBegin(1), isEnd(1);
	while (S[s_i] == '(')
	{
		s_i++;
		isBegin.back() = true;
	}
	num.push_back(S[s_i] - '0');
	s_i++;
	while (S[s_i] == ')')
	{
		s_i++;
		isEnd.back() = true;
	}
	std::vector<char> operators;
	while (s_i < (int)S.size())
	{
		operators.push_back(S[s_i]);
		s_i++;
		isBegin.push_back(false);
		while (S[s_i] == '(')
		{
			isBegin.back() = true;
			s_i++;
		}
		num.push_back(S[s_i] - '0');
		s_i++;
		isEnd.push_back(false);
		while (s_i < (int)S.size() && S[s_i] == ')')
		{
			isEnd.back() = true;
			s_i++;
		}
	}
	using vi = std::vector<int64_t>;
	using vvi = std::vector<vi>;
	int size{(int)num.size()};
	vvi minTable(size + 1, vi(size + 1, 1ll << 60)), maxTable(size + 1, vi(size + 1, -(1ll << 60)));
	for (int i{}; i < size; i++)
		minTable[i][i + 1] = maxTable[i][i + 1] = num[i];
	for (int width{2}; width <= size; width++)
		for (int left{}; left + width <= size; left++)
		{
			int right{left + width};
			if (isEnd[left] || isBegin[right - 1]) continue;
			for (int mid{left + 1}; mid < right; mid++)
			{
				if (operators[mid - 1] == '+')
				{
					minTable[left][right] = std::min(minTable[left][right], minTable[left][mid] + minTable[mid][right]);
					maxTable[left][right] = std::max(maxTable[left][right], maxTable[left][mid] + maxTable[mid][right]);
				}
				else
				{
					minTable[left][right] = std::min(minTable[left][right], minTable[left][mid] - maxTable[mid][right]);
					maxTable[left][right] = std::max(maxTable[left][right], maxTable[left][mid] - minTable[mid][right]);
				}
			}
		}
	return {minTable[0][size], maxTable[0][size]};
}

```