Problem: You have a grid with $H$ rows and $W$ columns. $H + W$ is even. We denote the cell at the $i$-th row from the top and the $j$-th column from the left by ($i, j$). In any cell ($i, j$), an integer between $1$ and $9$ is written if $i+j$ is even, and either '+' or '*' is written if $i+j$ is odd.

You can get a mathematical expression by moving right or down $H + W - 2$ times from ($1, 1$) to ($H, W$) and concatenating all the characters written in the cells you passed in order. Your task is to maximize the calculated value of the resulting mathematical expression by choosing an arbitrary path from ($1, 1$) to ($H, W$). If the maximum value is $10^{15}$ or less, print the value. Otherwise, print $-1$.



Input

The input consists of a single test case in the format below.


$H$ $W$
$a_{1,1}$ ... $a_{1,W}$
...
$a_{H,1}$ ... $a_{H,W}$


The first line consists of two $H$ integers and $W$ ($1 \leq H, W \leq 50$). It is guaranteed that $H + W$ is even. The following $H$ lines represent the characters on the grid. $a_{i,j}$ represents the character written in the cell ($i, j$). In any cell ($i, j$), an integer between $1$ and $9$ is written if $i+j$ is even, and either '+' or '*' is written if $i+1$ is odd.

Output

Print the answer in one line.

Examples

Input

3 3
1+2
+9*
1*5


Output

46


Input

1 31
9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9


Output

-1


Input

5 5
2+2+1
+1+1+
1+2+2
+1+1+
1+1+2


Output

10


Input

9 7
8+9*4*8
*5*2+3+
1*3*2*2
*5*1+9+
1+2*2*2
*3*6*2*
7*7+6*5
*5+7*2+
3+3*6+8


Output

86408

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 50

struct Info{
	Info(){
		row = col = 0;
		value = 0;
	}

	Info(int arg_row,int arg_col,ll arg_value){
		row = arg_row;
		col = arg_col;
		value = arg_value;
	}
	bool operator<(const struct Info &arg) const{
		return value < arg.value;
	}
	int row,col;
	ll value;
};


int H,W;
int diff_row[2] = {0,1},diff_col[2] = {1,0};
ll const LIMIT = 1000000000000000;
ll dp[NUM][NUM][NUM][NUM],final_dp[NUM][NUM];
vector<Info> G[NUM][NUM];
char base_map[NUM][NUM+1];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

int main(){

	scanf("%d %d",&H,&W);

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
	}

	for(int start_row = 0; start_row <= H-1; start_row++){
		for(int start_col = 0; start_col <= W-1; start_col++){
			for(int end_row = start_row; end_row <= H-1; end_row++){
				for(int end_col = start_col; end_col <= W-1; end_col++){
					dp[start_row][start_col][end_row][end_col] = -1;
				}
			}
		}
	}

	dp[H-1][W-1][H-1][W-1] = base_map[H-1][W-1]-'0';

	queue<Info> Q;
	int adj_row,adj_col;

	for(int start_row = H-1; start_row >= 0; start_row--){
		for(int start_col = W-1;start_col >= 0; start_col--){
			if(base_map[start_row][start_col] == '+' || base_map[start_row][start_col] == '*')continue;
			if(start_row == H-1 && start_col == W-1)continue;

			//右か下に進む
			for(int i = 0; i < 2; i++){
				adj_row = start_row+diff_row[i];
				adj_col = start_col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				Q.push(Info(adj_row,adj_col,base_map[start_row][start_col]-'0'));
			}

			while(!Q.empty()){

				if(base_map[Q.front().row][Q.front().col] >= '0' && base_map[Q.front().row][Q.front().col] <= '9'){

					for(int end_row = Q.front().row; end_row <= H-1; end_row++){
						for(int end_col = Q.front().col; end_col <= W-1; end_col++){
							if(dp[Q.front().row][Q.front().col][end_row][end_col] == -1)continue;

							dp[start_row][start_col][end_row][end_col] = max(dp[start_row][start_col][end_row][end_col],
									dp[Q.front().row][Q.front().col][end_row][end_col]*Q.front().value);

							if(dp[start_row][start_col][end_row][end_col] > LIMIT){
								printf("-1\n");
								return 0;
							}
						}
					}

				}else{

					if(base_map[Q.front().row][Q.front().col] == '+'){
						dp[start_row][start_col][Q.front().row][Q.front().col] = max(dp[start_row][start_col][Q.front().row][Q.front().col],Q.front().value);
					}else{

						for(int i = 0; i < 2; i++){
							adj_row = Q.front().row+diff_row[i];
							adj_col = Q.front().col+diff_col[i];

							if(!rangeCheck(adj_row,adj_col))continue;

							Q.push(Info(adj_row,adj_col,Q.front().value));
						}
					}
				}

				Q.pop();
			}
		}
	}

	for(int start_row = 0; start_row <= H-1; start_row++){
		for(int start_col = 0; start_col <= W-1; start_col++){
			for(int end_row = start_row; end_row <= H-1; end_row++){
				for(int end_col = start_col; end_col <= W-1; end_col++){
					if(dp[start_row][start_col][end_row][end_col] != -1){
						G[start_row][start_col].push_back(Info(end_row,end_col,dp[start_row][start_col][end_row][end_col]));
					}
				}
			}
		}
	}

	for(int row = 0; row <= H-1; row++){
		for(int col = 0; col <= W-1; col++)final_dp[row][col] = 0;
	}

	priority_queue<Info> PQ;
	int next_row,next_col;

	for(int i = 0; i < G[0][0].size(); i++){
		next_row = G[0][0][i].row;
		next_col = G[0][0][i].col;

		final_dp[next_row][next_col] = G[0][0][i].value;
		PQ.push(Info(next_row,next_col,final_dp[next_row][next_col]));
	}


	Info info;

	while(!PQ.empty()){

		if(PQ.top().row == H-1 && PQ.top().col == W-1){
			PQ.pop();
		}else if(PQ.top().value < final_dp[PQ.top().row][PQ.top().col]){
			PQ.pop();
		}else{

			info = PQ.top();
			PQ.pop();

			for(int i = 0; i < 2; i++){
				adj_row = info.row+diff_row[i];
				adj_col = info.col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				for(int k = 0; k < G[adj_row][adj_col].size(); k++){
					next_row = G[adj_row][adj_col][k].row;
					next_col = G[adj_row][adj_col][k].col;

					if(final_dp[next_row][next_col] < info.value+G[adj_row][adj_col][k].value){
						final_dp[next_row][next_col] = info.value+G[adj_row][adj_col][k].value;
						PQ.push(Info(next_row,next_col,final_dp[next_row][next_col]));
					}
				}
			}
		}
	}

	if(final_dp[H-1][W-1] > LIMIT){
		printf("-1\n");
	}else{
		printf("%lld\n",final_dp[H-1][W-1]);
	}

	return 0;
}