#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

struct Edge {
	int src;
	int dst;
	long long int cost;
};
using Graph=vector<vector<Edge>>;

class Centroid {
public:
	int dfs(const Graph&g, const int now, const int from, vector<int>&ch_nums, const vector<int>&oks) {
		int sum = 1;
		for (auto &&e : g[now]) {
			if (e.dst == from || oks[e.dst]!=-1)continue;
			else {
				sum += dfs(g, e.dst, e.src, ch_nums,oks);
			}
		}
		return ch_nums[now] = sum;
	};


	int find_centroid(const int asize, const vector<vector<Edge>>&graph, const int pre_root, const int pre_from, const vector<int>&ch_nums, const vector<int>&oks) {
		for (auto&& e : graph[pre_root]) {
			if (e.dst == pre_from)continue;
			if (oks[e.dst]!=-1)continue;
			if (ch_nums[e.dst]>asize / 2)return find_centroid(asize, graph, e.dst, e.src, ch_nums, oks);
		}
		return pre_root;
	}

	//void dfs2(const Graph&g, const int now, const int from,vector<long long int>&lens,const int root_id, long long int nlen) {
	//	lens.push_back(nlen);
	//	mp[make_pair(root_id,now)]=nlen;
	//	for (auto &&e : g[now]) {
	//		if (e.dst == from || oks[e.dst] != -1)continue;
	//		else {
	//			dfs2(g,e.dst,e.src,lens,root_id,nlen+e.cost);
	//		}
	//	}
	//}

	void cent(const vector<vector<Edge>>&graph, vector<int>&oks, const int root, const int from, vector<vector<int>>&centroid_edges, int& fst_centroid,int depth,vector<int>&ch_nums) {
dfs(graph, root, from, ch_nums, oks);

		int cent_id = find_centroid(ch_nums[root], graph, root, from, ch_nums, oks);

		
		//dfs2(graph,cent_id,from,lens[cent_id],0);
		sort(lens[cent_id].begin(),lens[cent_id].end());

		oks[cent_id] = depth;
		if (from != -1) {
			centroid_edges[from].push_back(cent_id);
		}
		else {
			fst_centroid = cent_id;
		}
		for (auto e : graph[cent_id]) {
			if (e.dst == from)continue;
			if (oks[e.dst]!=-1)continue;
			cent(graph, oks, e.dst, e.src, centroid_edges, fst_centroid,depth+1,ch_nums);
		}
	}

public:


	vector<vector<long long int>>lens;
	vector<vector<int>> centroid_graph;
	vector<int>parents;
	vector<int>oks;
	map<pair<int,int>,long long int>mp;

	//fst:root  snd:centroid_graph
	vector<vector<int>> get_cent_parent(const Graph&g) {
		lens.resize(g.size());
		oks=vector<int>(g.size(),-1);
		int root = -1;
		centroid_graph.resize(g.size());
		parents=vector<int>(g.size(),-1);
		vector<int>ch_nums(g.size());
		cent(g, oks, 0, -1, centroid_graph, root,0,ch_nums);

		for (int i = 0; i < centroid_graph.size(); ++i) {
			for (auto&& e : centroid_graph[i]) {
				parents[e] = i;
			}
		}
		return centroid_graph;
	}
}centroid;


void addEdge(Graph& g ,int a, int b,long long int c) {
	g[a - 1].push_back(Edge{ a - 1,b - 1,c });
	g[b - 1].push_back(Edge{ b - 1,a - 1,c });
}

vector<int>nums;
vector<int>ls;
vector<int>rs;
vector<int>pluss;
vector<vector<pair<int,int>>>memo;

string st;
void term(int&a,int&k) {
	nums.push_back(0);
	ls.push_back(0);
	rs.push_back(0);
	while (a != st.size() && st[a] == '(') {
		ls[k]=true;
		a++;
	}
	nums[k]=st[a]-'0';
	a++;
	while (a != st.size() && st[a] == ')') {
		rs[k]=true;
		a++;
	}
	k++;
	return ;
}
void expr(int &a) {
	int k=0;
	term(a,k);

	while (a != st.size()) {
		pluss.push_back(st[a]=='+');
		a++;
		term(a,k);
	}
}
void init() {
	int a=0;
	expr(a);
	memo=vector<vector<pair<int,int>>>(nums.size()+1,vector<pair<int,int>>(nums.size()+1,make_pair(1e9,-1e9)));
}

pair<int,int> solve(int l, int r) {
	if(memo[l][r].first!=1e9)return memo[l][r];
	 if(l+1==r)return memo[l][r]=make_pair(nums[l],nums[l]);
	 if (l + 2 == r) {
		 if(rs[l]||ls[l+1])return memo[l][r]=make_pair(1e8,-1e8);
		 else {
			 if (pluss[l]) {
				 return memo[l][r]=make_pair(nums[l]+nums[l+1],nums[l]+nums[l+1]);
			 }
			 else {
				 return memo[l][r]=make_pair(nums[l]-nums[l+1],nums[l]-nums[l+1]);
			 }
		 }
	 }
	 else {
		 pair<int,int>ans=make_pair(1e8,-1e8);
		 if(rs[l]||ls[r-1])return make_pair(1e8,-1e8);
		 for (int k = l + 1; k < r; ++k) {
			 bool ok=true;
			//if(ls[k-1])ok=false;
			 if(!ok)continue;
			 else {
				 auto lp=solve(l,k),rp=solve(k,r);

				 if (pluss[k - 1]) {
					 auto p=make_pair(lp.first+rp.first,lp.second+rp.second);
					 ans=make_pair(min(ans.first,p.first),max(ans.second,p.second));
				 }
				 else {
					 auto p=make_pair(lp.first-rp.second,lp.second-rp.first);
					 ans=make_pair(min(ans.first,p.first),max(ans.second,p.second));
				 }
			 }
		 }
		 return memo[l][r]=ans;
	 }
}

int main()
{
	cin>>st;
	init();
	auto p=solve(0,nums.size());
	cout<<p.second<<endl;
	return 0;
}

### Prompt

In CPP, your task is to solve 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"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

struct Edge {
	int src;
	int dst;
	long long int cost;
};
using Graph=vector<vector<Edge>>;

class Centroid {
public:
	int dfs(const Graph&g, const int now, const int from, vector<int>&ch_nums, const vector<int>&oks) {
		int sum = 1;
		for (auto &&e : g[now]) {
			if (e.dst == from || oks[e.dst]!=-1)continue;
			else {
				sum += dfs(g, e.dst, e.src, ch_nums,oks);
			}
		}
		return ch_nums[now] = sum;
	};


	int find_centroid(const int asize, const vector<vector<Edge>>&graph, const int pre_root, const int pre_from, const vector<int>&ch_nums, const vector<int>&oks) {
		for (auto&& e : graph[pre_root]) {
			if (e.dst == pre_from)continue;
			if (oks[e.dst]!=-1)continue;
			if (ch_nums[e.dst]>asize / 2)return find_centroid(asize, graph, e.dst, e.src, ch_nums, oks);
		}
		return pre_root;
	}

	//void dfs2(const Graph&g, const int now, const int from,vector<long long int>&lens,const int root_id, long long int nlen) {
	//	lens.push_back(nlen);
	//	mp[make_pair(root_id,now)]=nlen;
	//	for (auto &&e : g[now]) {
	//		if (e.dst == from || oks[e.dst] != -1)continue;
	//		else {
	//			dfs2(g,e.dst,e.src,lens,root_id,nlen+e.cost);
	//		}
	//	}
	//}

	void cent(const vector<vector<Edge>>&graph, vector<int>&oks, const int root, const int from, vector<vector<int>>&centroid_edges, int& fst_centroid,int depth,vector<int>&ch_nums) {
dfs(graph, root, from, ch_nums, oks);

		int cent_id = find_centroid(ch_nums[root], graph, root, from, ch_nums, oks);

		
		//dfs2(graph,cent_id,from,lens[cent_id],0);
		sort(lens[cent_id].begin(),lens[cent_id].end());

		oks[cent_id] = depth;
		if (from != -1) {
			centroid_edges[from].push_back(cent_id);
		}
		else {
			fst_centroid = cent_id;
		}
		for (auto e : graph[cent_id]) {
			if (e.dst == from)continue;
			if (oks[e.dst]!=-1)continue;
			cent(graph, oks, e.dst, e.src, centroid_edges, fst_centroid,depth+1,ch_nums);
		}
	}

public:


	vector<vector<long long int>>lens;
	vector<vector<int>> centroid_graph;
	vector<int>parents;
	vector<int>oks;
	map<pair<int,int>,long long int>mp;

	//fst:root  snd:centroid_graph
	vector<vector<int>> get_cent_parent(const Graph&g) {
		lens.resize(g.size());
		oks=vector<int>(g.size(),-1);
		int root = -1;
		centroid_graph.resize(g.size());
		parents=vector<int>(g.size(),-1);
		vector<int>ch_nums(g.size());
		cent(g, oks, 0, -1, centroid_graph, root,0,ch_nums);

		for (int i = 0; i < centroid_graph.size(); ++i) {
			for (auto&& e : centroid_graph[i]) {
				parents[e] = i;
			}
		}
		return centroid_graph;
	}
}centroid;


void addEdge(Graph& g ,int a, int b,long long int c) {
	g[a - 1].push_back(Edge{ a - 1,b - 1,c });
	g[b - 1].push_back(Edge{ b - 1,a - 1,c });
}

vector<int>nums;
vector<int>ls;
vector<int>rs;
vector<int>pluss;
vector<vector<pair<int,int>>>memo;

string st;
void term(int&a,int&k) {
	nums.push_back(0);
	ls.push_back(0);
	rs.push_back(0);
	while (a != st.size() && st[a] == '(') {
		ls[k]=true;
		a++;
	}
	nums[k]=st[a]-'0';
	a++;
	while (a != st.size() && st[a] == ')') {
		rs[k]=true;
		a++;
	}
	k++;
	return ;
}
void expr(int &a) {
	int k=0;
	term(a,k);

	while (a != st.size()) {
		pluss.push_back(st[a]=='+');
		a++;
		term(a,k);
	}
}
void init() {
	int a=0;
	expr(a);
	memo=vector<vector<pair<int,int>>>(nums.size()+1,vector<pair<int,int>>(nums.size()+1,make_pair(1e9,-1e9)));
}

pair<int,int> solve(int l, int r) {
	if(memo[l][r].first!=1e9)return memo[l][r];
	 if(l+1==r)return memo[l][r]=make_pair(nums[l],nums[l]);
	 if (l + 2 == r) {
		 if(rs[l]||ls[l+1])return memo[l][r]=make_pair(1e8,-1e8);
		 else {
			 if (pluss[l]) {
				 return memo[l][r]=make_pair(nums[l]+nums[l+1],nums[l]+nums[l+1]);
			 }
			 else {
				 return memo[l][r]=make_pair(nums[l]-nums[l+1],nums[l]-nums[l+1]);
			 }
		 }
	 }
	 else {
		 pair<int,int>ans=make_pair(1e8,-1e8);
		 if(rs[l]||ls[r-1])return make_pair(1e8,-1e8);
		 for (int k = l + 1; k < r; ++k) {
			 bool ok=true;
			//if(ls[k-1])ok=false;
			 if(!ok)continue;
			 else {
				 auto lp=solve(l,k),rp=solve(k,r);

				 if (pluss[k - 1]) {
					 auto p=make_pair(lp.first+rp.first,lp.second+rp.second);
					 ans=make_pair(min(ans.first,p.first),max(ans.second,p.second));
				 }
				 else {
					 auto p=make_pair(lp.first-rp.second,lp.second-rp.first);
					 ans=make_pair(min(ans.first,p.first),max(ans.second,p.second));
				 }
			 }
		 }
		 return memo[l][r]=ans;
	 }
}

int main()
{
	cin>>st;
	init();
	auto p=solve(0,nums.size());
	cout<<p.second<<endl;
	return 0;
}

```