Japan Alumni Group Summer Camp 2017 Day 3

E - Route Calculator


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 512MB

Problem Statement

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}$ $\cdots$ $a_{1,W}$ $\ldots$ $a_{H,1}$ $\cdots$ $a_{H,W}$

The first line consists of two integers $H$ and $W$ ($1 \le H,W \le 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+j$ is odd.

Output

Print the answer in one line.


Sample Input 1

3 3
1+2
+9*
1*5

Output for Sample Input 1

46

The maximum value is obtained by passing through the following cells: $(1,1)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,3)$.


Sample Input 2

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

Output for Sample Input 2

-1

You can obtain $9^{16}$, but it's too large.


Sample Input 3

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

Output for Sample Input 3

10

Sample Input 4

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 for Sample Input 4

86408

Submit提出する