Vanya is doing his maths homework. He has an expression of form <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/12fd75e59feeb788ff8b791f7194301b0d005ad6.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> are digits from 1 to 9, and sign <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/5535bcdec4c47f48bc7dcaaf51ba2b5901a202e5.png" style="max-width: 100.0%;max-height: 100.0%;"/> represents either a plus '+' or the multiplication sign '*'. Vanya needs to add one pair of brackets in this expression so that to maximize the value of the resulting expression.
The first line contains expression *s* (1 ≤ |*s*| ≤ 5001, |*s*| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs  +  and  * . 

The number of signs  *  doesn't exceed 15.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back

typedef long long ll;

using namespace std;
ll a[6000],b[6000];
vector <ll> f;
string s,t;
pair<ll,ll> hesab(ll l, ll r){
	ll x = 0, y = a[l];
	for (int i = l; i < r; i++)
		if (b[i] == 1)
		   x += y, y = a[i + 1];
		else
			y *= a[i + 1];
	return mp(x , y);
}
int main()
{
    string s;
	cin >> s;
	ll i = 0, j = 0, n = 0 ,x = 0 ,y = 0 ,m = 0,k = 0,ans = 0;
    s.insert(0,"1*");
    s = s + "*1";
	n = s.size();
	m = n / 2;
	for (i = 0; i < n; i += 2){
		a[i / 2] = s[i] - 48;
	}
	for (i = 1; i < n; i += 2){
		if (s[i] == '+'){
		   b[i / 2] = 1;
		}
		else
		{
			b[i / 2] = 2;
			f.pb(i / 2);
		}

	}
	for (i = 0; i < f.size(); i++){
		for (j = i + 1; j < f.size(); j++){
		 pair <ll,ll> tmp = hesab(0,f[i]);
		 x = tmp.first;
		 y = tmp.second;
		 tmp = hesab(f[i]+1,f[j]);
		 y *= tmp.first + tmp.second;
		 ll xx = a[f[j]];
		 a[f[j]] = y;
		 tmp = hesab(f[j],m);
		 ans = max(ans, x + tmp.first + tmp.second);
		 a[f[j]] = xx;
		}
	}
	if (ans == 0) {
        for (int i = 1; i <= (n - 1) / 2; i++) {
            ans += a[i];
            }
        }
	cout << ans << endl;
	return 0;
}

			  		  	  	 					 		 	  		 		