경로 계산기

시간 제한2초메모리 제한512 MB

요약

오른쪽과 아래로만 이동하는 경로를 골라 숫자와 연산자로 이뤄진 식의 최댓값을 구합니다. 값이 10^15를 넘으면 -1을 출력합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열, 수학
정답자: 아직 제출이 없습니다

문제

$H$ 행 $W$ 열의 격자가 있다. $H+W$ 는 짝수이다. 위에서 $i$ 번째 행, 왼쪽에서 $j$ 번째 열의 칸을 $(i, j)$ 로 나타낸다. $i+j$ 가 짝수인 칸에는 1 이상 9 이하의 정수가 적혀 있고, $i+j$ 가 홀수인 칸에는 + 또는 *가 적혀 있다.

$(1,1)$ 에서 출발해 오른쪽 또는 아래로 $H+W-2$ 번 이동하여 $(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$ 줄에 격자의 문자가 주어진다.

출력

답을 한 줄에 출력한다.

예제4

예제 1
입력
```
3 3
1+2
+9*
1*5
```
예상 출력
```
46
```

예제 2

입력

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

예상 출력

-1

예제 3
입력
```
5 5
2+2+1
+1+1+
1+2+2
+1+1+
1+1+2
```
예상 출력
```
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

예상 출력