#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int,int> P;
typedef pair<P,int> P1;

map<P1,int> memo;
string s;

int dfs(int l, int r, int flag){
  
  if( memo.count(P1(P(l,r),flag)) ) return memo[P1(P(l,r),flag)];
  
  int L = l, R = r;
  
  int cnt = 0;
  
  for(int i=L;i<=R;i++){
    if( '0' <= s[i] && s[i] <= '9' ) cnt++;
  }
  
  if( cnt == 1 ){
    if( R - L + 1 == 1 ) return memo[P1(P(L,R),flag)] = s[L] - '0';
    else return memo[P1(P(L,R),flag)] = flag == 0 ? -1e9 : 1e9;
  }
  
  while( s[L] == '(' ) L++;
  
  while( s[R] == ')' ) R--;
  
  int res = flag == 0 ? -1e9 : 1e9;
  
  for(int i=L;i<=R;i++){
    
    if( s[i] == '+' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, flag );
      if( flag == 0 ) res = max( res, A + B );
      else res = min( res, A + B );
    }
    
    if( s[i] == '-' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, !flag );
      if( flag == 0 ) res = max( res, A - B );
      else res = min( res, A - B );
    }
    
  }
  
  return memo[P1(P(l,r),flag)] = res;
}

signed main(){
  
  cin>>s;
  
  cout<<dfs(0,(int)s.size()-1,0)<<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>
#define int long long
using namespace std;

typedef pair<int,int> P;
typedef pair<P,int> P1;

map<P1,int> memo;
string s;

int dfs(int l, int r, int flag){
  
  if( memo.count(P1(P(l,r),flag)) ) return memo[P1(P(l,r),flag)];
  
  int L = l, R = r;
  
  int cnt = 0;
  
  for(int i=L;i<=R;i++){
    if( '0' <= s[i] && s[i] <= '9' ) cnt++;
  }
  
  if( cnt == 1 ){
    if( R - L + 1 == 1 ) return memo[P1(P(L,R),flag)] = s[L] - '0';
    else return memo[P1(P(L,R),flag)] = flag == 0 ? -1e9 : 1e9;
  }
  
  while( s[L] == '(' ) L++;
  
  while( s[R] == ')' ) R--;
  
  int res = flag == 0 ? -1e9 : 1e9;
  
  for(int i=L;i<=R;i++){
    
    if( s[i] == '+' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, flag );
      if( flag == 0 ) res = max( res, A + B );
      else res = min( res, A + B );
    }
    
    if( s[i] == '-' ){
      int A = dfs( L, i - 1, flag );
      int B = dfs( i + 1, R, !flag );
      if( flag == 0 ) res = max( res, A - B );
      else res = min( res, A - B );
    }
    
  }
  
  return memo[P1(P(l,r),flag)] = res;
}

signed main(){
  
  cin>>s;
  
  cout<<dfs(0,(int)s.size()-1,0)<<endl;
  
  return 0;
}


```