Vanya is doing his maths homework. He has an expression of form , where x1,?x2,?...,?xn are digits from 1 to 9, and sign 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.
Input
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.
Output
In the first line print the maximum possible value of an expression.
Examples
Input
3+5*7+8*4
Output
303
Input
2+3*5
Output
25
Input
3*4*5
Output
60
Note
Note to the first sample test. 3?+?5?*?(7?+?8)?*?4?=?303.
Note to the second sample test. (2?+?3)?*?5?=?25.
Note to the third sample test. (3?*?4)?*?5?=?60 (also many other variants are valid, for instance, (3)?*?4?*?5?=?60).
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>using namespace std;typedef long long ll;
long long ans, t, n, m;
string str, s;
vector<int> vec;
stack<ll> sc, sn;
struct node {int x, y;
} no[2005];
long long result(long long a, long long b, char c) {return (c == '*') ? a * b : a + b;
}
void cal() {char t = sc.top();sc.pop();long long a = sn.top();sn.pop();long long b = sn.top();sn.pop();sn.push(result(a, b, t));
}
long long expression(string s) {for(int i = 0; i < s.size(); i++) {char c = s[i];if(isdigit(c)) {sn.push(c - '0');} else if(c == '(') {sc.push(c);} else if(c == ')') {while(sc.top() != '(') {cal();}sc.pop();} else {if(c == '+') {while(!sc.empty() && sc.top() == '*') {cal();}sc.push(c);} else {sc.push(c);}}}while(!sc.empty()) {cal();}return sn.top();
}
int main() {cin >> str;n = str.size();vec.push_back(-1);for(int i = 1; i < n; i += 2) {if(str[i] == '*') {vec.push_back(i);}}vec.push_back(n);int len = vec.size();ans = 0;for(int i = 0; i < len - 1; i++) {for(int j = i + 1; j < len; j++) {s = str;s.insert(vec[i] + 1, 1, '(');s.insert(vec[j] + 1, 1, ')');ans = max(ans, expression(s));}}cout << ans << endl;
}