TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

24.2% (8/33)

Tags

Description

仰望完了星空,

楓音轉頭望向妁艷,

「妁艷~♥ 妁艷~♥」

毫無反應,只是個妁艷。

這時楓音感到心急如焚,難道說妁艷的體力不支了?

難道說妁艷已經沒有了魔力嗎!?

楓音急忙的抱起妁艷,狂奔到了保健室去,將妁艷放到了床上。

「唔...唔...」楓音十分的慌張,看著保健室究竟有什麼東西能讓妁艷醒來...

只見妁艷的氣息越來越薄弱,楓音幾乎已經沒有辦法了...

這時,楓音嘆了氣,默默的將胸口中的小盒子拿了出來......

這小盒子是他爺爺留給楓音的,小盒子中放著的是他們家代代相傳,能量強大的魔法石

楓音一直以為那只是堆漂亮的珠寶玩具而已,直到剛才,才知道原來這就是傳說中的魔法石,維繫他們家族命運的東西...

將魔法石拿了出來,在妁艷身旁擺出了魔法石陣,

楓音深深的吸了一口氣,希望他的魔力...足夠讓妁艷醒來...

足夠讓妁艷...醒來之後再戰鬥。

魔法石陣的啟動是個十分複雜的過程。

它是以在中央N*N個魔法石所組成的正方形為能量來源,以魔力填充整個空間。

每個魔法石都有一個魔力值M。

魔法石陣十分強大,理所當然的想要啟動這個魔法石陣也十分的困難。

施術者必須擁有一定的魔力,並且還要有一定的觸發條件...

所謂的觸發條件就是所謂的魔法式

施術者必須從最左上角的魔法石開始,以魔力絲連接各個魔法石,使得魔力絲最後連接的到最右下角的魔法石。

魔力絲只能從一個魔法石連接到其上下左右四個方位的另一個魔法石。

當完成了魔法式的連結之後,就要注入魔力來啟動這麼魔法石陣了。

啟動這個魔法石陣的所需的魔力是由魔力絲連結的魔法石中魔力值最大的減去魔力值最小的。

啟動了之後妁艷就有機會醒來了,可是...卻不一定能回復到他的最顛峰狀態。

所以楓音希望可以消耗盡量少的魔力,使得妁艷醒來之後,能幫他補充盡量多的魔力。

請問楓音最少需要耗費多少魔力值呢?

Input Format

第1行有一個N
N<=150

接下來第2行~第n-1行每行有N個數字,分別代表在(0,0)至(n-1,n-1)的魔法石的魔力值M(i,j)
0<=M(i,j)<=400

Output Format

請輸出所需的最低魔力值

Sample Input

5
1 5 5 7 8
3 3 7 10 1
4 9 7 5 6
4 8 1 6 3
9 8 9 10 6

Sample Output

6

Hints

從最左上角(0,0)魔力值為1的魔法石開始
經過
(0,1)魔力值3
(1,1)魔力值3
(2,1)魔力值7
(2,2)魔力值7
(2,3)魔力值1
(3,3)魔力值6
(4,3)魔力值3
到達
(4,4)魔力值6

所需魔力為(7-1)=6

Problem Source

原TIOJ1763 / problem setter:jeremy89183

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10