香蕉，作為一種方便食用又能快速補充能量的食物，和巧克力一樣受到全國爬山大賽
（National Pa Shan Contest，簡稱 NPSC）選手的歡迎。一般來說 NPSC 主辦單位會在比賽場地的各處設置領取香蕉的地點，讓選手們隨時隨地都可以吃到香蕉。然而，今年因為人力不足，比賽場地裡只有一個領取香蕉的地點，而且毫不意外地永遠都大排長龍。
舊乙作為一個香蕉愛好者，比賽中沒有香蕉吃是絕對不行的。因此，他事先仔細研究了香蕉領取處：香蕉領取處前方是一個巨大的有 N 個橫列與 M 個直行的棋盤，排隊時，棋盤的每個格子上永遠都會有恰一個人，並且每個格子 (i,j) 的地面上都寫了一個數字 ai,j，代表格子
(i,j) 上的人就是隊伍中的第 ai,j 個人。格子 (i,j) 指的是位於第 i 個橫列與第 j 個直行的格子。
數字差 1 的格子一定是相鄰（共用一條邊）的。香蕉的發放很有效率，每過一秒鐘，在寫著數字 1 的格子上的人就會領到香蕉並離開隊伍，而其他人會移動到下一個格子去，也就是說本來在寫著數字 x 的格子上的人，會移動到寫著 x − 1 的格子。與此同時，會有一個新的想要香蕉的人來排隊，他會排在寫著數字 N × M 的格子上。寫著數字 1 和數字 N × M 的格子一定會在這個棋盤的邊界，才不會有人需要穿越長長的隊伍。
舊乙現在成功排入了這個隊伍，他目前在寫著數字 N × M 的格子上。照理來說，他要等待 N × M 秒才能拿到香蕉，但他現在迫切地需要香蕉。因此，他決定使出他的絕招——插隊！
假設舊乙現在在格子 (x,y) 上，那麼對於和 (x,y) 相鄰的格子 (i,j)，只要滿足 |ax,y −ai,j| ̸= 1，也就是那個格子既不是前一個格子，也不是下一個格子，那麼舊乙就可以偷偷地插隊到格子 (i,j) 上，同樣要花費 1 秒鐘。聽起來很美好，但也不是完全沒有代價，這麼做的時候舊乙要承受 ci,j 的風險值，如果他在整個排隊的過程中，承受的風險值超過 B，那麼他就會因為插隊被主辦單位取消比賽資格。
要是被取消資格就得不償失了（他甚至連香蕉也拿不到），請你幫他計算在不會被取消資格的前提下，他至少要花幾秒才能領到香蕉。
舉例來說，當 N = 5,M = 6,B = 11 時，下圖是香蕉領取處前的棋盤示意圖。大黑色數字是每個格子上寫的數字，右下角的小灰色數字則是插隊到那個格子需要承受的風險值。灰色實線路線是在完全不插隊的情況下，領取香蕉的正常路線，虛線路線則是一種總風險值為 10 的舊乙可能的移動路線。
輸入的第一行有三個整數 N,M,B，表示棋盤的大小與舊乙最大能承受的總風險值。
接下來有 N 行，其中第 i 行包含 M 個正整數 ai,1,ai,2,...,ai,M，ai,j 表示格子 (i,j) 上寫著的數字。
再來有 N 行，其中第 i 行包含 M 個正整數 ci,1,ci,2,...,ci,M，ci,j 表示插隊到格子 (i,j) 時舊乙需要承受的風險值。
輸出一行，包含一個整數，表示舊乙在不會被取消資格的前提下，至少要花幾秒才能拿到香蕉。
4 4 5 12 11 2 1 13 10 3 4 14 9 8 5 15 16 7 6 5 5 4 4 3 5 1 5 2 5 2 4 4 4 3 2
8
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||