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
inputCopy
3+5*7+8*4
outputCopy
303
inputCopy
2+3*5
outputCopy
25
inputCopy
3*4*5
outputCopy
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
using namespace std;
#define maxn 500005
#define inf 0x3f3f3f3f
typedef long long ll;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b){
if(b%2)ans=ans*a;
a=a*a;
b=b/2;
}
return ans;
}
vector pos;
stacknum;
stack ch;
ll cal(string s)
{
while(!num.empty())num.pop();
while(!ch.empty())ch.pop();
for(int i=0;i='0'&&c>str){
int n=str.size();
pos.clear();
pos.push_back(-1);
for(int i=1;i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
