TopCoder

aacpschool

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

作為一個競速破關玩家 (speedrunner)，你對「撿金幣」遊戲地圖瞭若指掌。一開始玩家會從左上角 $(0,0)$ 開始，並走到右下角 $(N-1, M-1)$ 再回到 $(0,0)$ 算過關。每次只能移動到相鄰的格子，相鄰格子是指有共同邊。在某些格子上有障礙物，有障礙物的格子不能經過，而在沒有障礙物的格子上有些有一枚金幣，經過就可以搜集金幣。

因為你的目標還是 speedrun，你要在 $2(N+M-2)$ 秒過關，你想知道在此條件下，最多能搜集多少金幣。

Input Format

輸入第一行有兩個空白分的正整數 $N, M$，分別表示地圖的長寬。
接下來的 $N$ 行，每一行都有 $M$ 個空白分隔的整數 $a_{ij}$，當 $a_{ij} = 0$ 時表示該格是普通格子，$a_{ij} = 1$ 時表示該格有金幣，$a_{ij} = -1$ 時表示該格有障礙物。

輸入保證 $1\le N, M\le 100$，$-1\le a_{ij}\le 1$。

Output Format

請輸出一個整數代表最多可搜集的金幣。請注意有可能你無論如何都無法在 $2(N+M-2)$ 秒內通關，此時請輸出 $0$。

Sample Input 1

2 3
1 0 -1
1 0 1

Sample Output 1

Hints

Problem Source

北市賽

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~15	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2

810 . 競速破關