TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

44.0% (11/25)

Tags

Description

你統領著一群殭屍。
可是他們想吃大腦想到瘋了,你知道再不餵他們吃大腦,下一個被吃的就是你的大腦了。所以你開始尋找適合的人家。

現在你已經帶領著殭屍大軍到他們家門口前了。

他們家的花圃是一個N * M的草坪,但是每個位置都有很多兇惡的植物們。但是你已經事先得知了他們家的草坪配置圖,如下圖所示:

5 9 1 1 2 1
1 2 4 5 1 6
4 1 2 7 1 1
1 5 0 0 1 9

每個位置代表為了清除那株植物你需要犧牲掉幾隻殭屍才能把那株植物剷除並往下一格走。而當然,只要能走到地圖最左邊你的殭屍就會吃到一顆新鮮的大腦。
當然一行的終點只有一顆大腦可以吃。

你的殭屍當然不像遊戲《Plants vs Zombies》中的那麼笨只走直線,牠們屍可以上下左右移動,但是要注意的是這個花園的地板很脆弱,每個格子只能走過一次,
因為把植物吃掉之後沒有植物根部的抓地力,走上去會土質流失。

現在給你殭屍大軍的數量,請問最多可以吃到幾顆大腦。

※注意:就算把最左邊一排的植物剛好吃掉,要走到終點吃掉大腦還需要一隻殭屍,例如假設走最上面那一行(5 9 1 1 2 1 那行),那麼至少需要
( 5+9+1+1+2+1 ) +1隻殭屍才能吃到大腦。

※殭屍必從每列的最右方出發。

Input Format

輸入第一行包含三個正整數,代表花園的長 N 和寬 M 及你的殭屍大軍數量Z (1≦N,M≦50 ; N*M≦400 ; Z≦20000000)
接下來會有 N 行,每行包含 M 個正整數。

第i行第j個數字 Kij 表示你要吃掉那格植物必須要花多少殭屍 (0≦Kij≦100000)

Output Format

對每一筆輸入資料,輸出一個正整數表示最大可以吃到的大腦數量。

如果吃不到任何大腦,請輸出 "THE ZOMBIES ATE MY BRAIN" (不含雙引號)。

Sample Input

4 6 23
5 9 1 1 2 1
1 2 4 5 1 6
4 1 2 7 1 1
1 5 0 0 1 9

Sample Output

2

Hints


5 9 o o o o
o o o 5 1 6
4 1 2 7 x x
x x x x x 9

如上圖為兩條吃大腦的路徑。
需求殭屍數 = (1+1+1+0+0+1+5)+1 + (1+2+1+1+4+2+1)+1 = 10 + 13=23

Problem Source

原TIOJ1588 / Problem Setter: poao(ATP)
題材來源: 《Plants vs Zombies》

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 2000 65536 262144
2 2000 65536 262144
3 2000 65536 262144
4 2000 65536 262144