#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 200

enum Type{
	MAX,
	MIN,
};

char buf[NUM+5];
int dp[NUM][NUM][2];
int num_count,op_count;
int num_loc[NUM],op_loc[NUM];

bool is_digit(char ch){
	return ch >= '0' && ch <= '9';
}

bool is_op(char ch){
	return ch == '+' || ch == '-';
}


int main(){

	scanf("%s",buf);

	num_count = 0,op_count = 0;
	for(int i = 0; buf[i] != '\0'; i++){
		if(is_digit(buf[i])){
			num_loc[num_count++] = i;
		}else if(is_op(buf[i])){
			op_loc[op_count++] = i;
		}
	}

	for(int left = 0; left < num_count; left++){
		dp[left][left][MAX] = buf[num_loc[left]]-'0';
		dp[left][left][MIN] = buf[num_loc[left]]-'0';
		for(int right = left+1; right < num_count; right++){
			dp[left][right][MAX] = -BIG_NUM;
			dp[left][right][MIN] = BIG_NUM;
		}
	}

	int right,left_left,left_right,right_left,right_right;

	for(int length = 2; length <= num_count; length++){
		for(int left = 0; left+length-1 < num_count; left++){
			right = left+length-1;

			for(int op = left; op < right; op++){
				left_left = left;
				left_right = op;

				right_left = op+1;
				right_right = right;

				if(left_left != left_right && (buf[num_loc[left_left]+1] == ')' || buf[num_loc[left_right]-1] == '('))continue;
				if(right_left != right_right && (buf[num_loc[right_left]+1] == ')' || buf[num_loc[right_right]-1] == '('))continue;

				if(buf[op_loc[op]] == '+'){
					dp[left][right][MAX] = max(dp[left][right][MAX],dp[left_left][left_right][MAX]+dp[right_left][right_right][MAX]);
					dp[left][right][MIN] = min(dp[left][right][MIN],dp[left_left][left_right][MIN]+dp[right_left][right_right][MIN]);
				}else{
					dp[left][right][MAX] = max(dp[left][right][MAX],dp[left_left][left_right][MAX]-dp[right_left][right_right][MIN]);
					dp[left][right][MIN] = min(dp[left][right][MIN],dp[left_left][left_right][MIN]-dp[right_left][right_right][MAX]);
				}
			}
		}
	}

	printf("%d\n",dp[0][num_count-1][MAX]);

	return 0;
}


### Prompt

Please provide a CPP coded solution to the problem described below:

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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 200

enum Type{
	MAX,
	MIN,
};

char buf[NUM+5];
int dp[NUM][NUM][2];
int num_count,op_count;
int num_loc[NUM],op_loc[NUM];

bool is_digit(char ch){
	return ch >= '0' && ch <= '9';
}

bool is_op(char ch){
	return ch == '+' || ch == '-';
}


int main(){

	scanf("%s",buf);

	num_count = 0,op_count = 0;
	for(int i = 0; buf[i] != '\0'; i++){
		if(is_digit(buf[i])){
			num_loc[num_count++] = i;
		}else if(is_op(buf[i])){
			op_loc[op_count++] = i;
		}
	}

	for(int left = 0; left < num_count; left++){
		dp[left][left][MAX] = buf[num_loc[left]]-'0';
		dp[left][left][MIN] = buf[num_loc[left]]-'0';
		for(int right = left+1; right < num_count; right++){
			dp[left][right][MAX] = -BIG_NUM;
			dp[left][right][MIN] = BIG_NUM;
		}
	}

	int right,left_left,left_right,right_left,right_right;

	for(int length = 2; length <= num_count; length++){
		for(int left = 0; left+length-1 < num_count; left++){
			right = left+length-1;

			for(int op = left; op < right; op++){
				left_left = left;
				left_right = op;

				right_left = op+1;
				right_right = right;

				if(left_left != left_right && (buf[num_loc[left_left]+1] == ')' || buf[num_loc[left_right]-1] == '('))continue;
				if(right_left != right_right && (buf[num_loc[right_left]+1] == ')' || buf[num_loc[right_right]-1] == '('))continue;

				if(buf[op_loc[op]] == '+'){
					dp[left][right][MAX] = max(dp[left][right][MAX],dp[left_left][left_right][MAX]+dp[right_left][right_right][MAX]);
					dp[left][right][MIN] = min(dp[left][right][MIN],dp[left_left][left_right][MIN]+dp[right_left][right_right][MIN]);
				}else{
					dp[left][right][MAX] = max(dp[left][right][MAX],dp[left_left][left_right][MAX]-dp[right_left][right_right][MIN]);
					dp[left][right][MIN] = min(dp[left][right][MIN],dp[left_left][left_right][MIN]-dp[right_left][right_right][MAX]);
				}
			}
		}
	}

	printf("%d\n",dp[0][num_count-1][MAX]);

	return 0;
}


```