问题描述

你有一个 $H$ 行 $W$ 列的网格。$H + W$ 是偶数。我们用 $(i, j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格。在任何单元格 $(i, j)$ 中，如果 $i + j$ 是偶数，则写入一个介于 $1$ 和 $9$ 之间的整数，如果 $i + j$ 是奇数，则写入 + 或 *。

你可以通过从 $(1,1)$ 移动右边或向下 $H + W - 2$ 次，将你经过的所有单元格中的字符按顺序连接起来，得到一个数学表达式。你的任务是通过从 $(1, 1)$ 到 $(H, W)$ 选择任意路径，使得计算得到的数学表达式的值最大化。如果最大值小于等于 $10^{15}$，则输出该值。否则，输出 $-1$。

输入

输入包含一个测试用例，格式如下所示。

$H$ $W$ $a_{1,1}$ $\cdots$ $a_{1,W}$ $\ldots$ $a_{H,1}$ $\cdots$ $a_{H,W}$

第一行包含两个整数 $H$ 和 $W$ ($1 \le H, W \le 50$)，保证 $H + W$ 是偶数。接下来的 $H$ 行表示网格中的字符。$a_{i,j}$ 表示单元格 $(i,j)$ 中的字符。在任何单元格 $(i, j)$ 中，如果 $i + j$ 是偶数，则写入一个介于 $1$ 和 $9$ 之间的整数，如果 $i + j$ 是奇数，则写入 + 或 *。

输出

输出一个整数，表示答案。

样例输入 1

3 3
1+2
+9*
1*5

样例输出 1

46

通过经过以下单元格，可以得到最大值：$(1,1)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,3)$。

样例输入 2

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

样例输出 2

-1

你可以得到 $9^{16}$，但它太大了。

样例输入 3

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

样例输出 3

10

样例输入 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

样例输出 4

86408