2013年9月18日 星期三

10350 - Liftless EME

EME 建築在 2002 年到 2020 年間越建越高,但是電梯數量仍維持定量。因此這對於學生到教室是個很重要的問題,對於 ACM 練習賽的選手特別重要,比賽從每個星期二的 2:00 pm 開始,此時電梯和樓梯都擠滿了實驗室的學生。

所有參賽選手打算抄捷徑到 ACM 教室,他們偷偷地在每一層天花板挖洞,並且每個洞向下放置一個樓梯,因此他們可以藉由這些到達另一個樓層,藉以避面大批人群。


問題為:現在有很多捷徑,計算一個最短路徑抵達目的地。

目標從地面 (0 層)  到達頂樓 (n-1 層),特別注意參賽者只會往上爬。

Input

輸入有多組測資。

對於每組測資,第一行會有一個測資組名稱,長度不超過 12 字元。

接著會有 2 個整數 n, m,分別表示 EME 建築的樓層數量、每一層有的洞數量。

接下來會有 m(n-1) 行,每行上會有 m 個整數,在第 k*m+i 行上,表示在第 k 層的第 i 個洞的資訊,該行的第 j 個整數表示到第 k+1 層的第 j 個洞的時間。

(0 <= k < n-1 < 120, 1 < i, j < m <= 15)

Output

對於每組測資輸出兩行,第一行為測資組名稱,第二行為最少時間從地面到頂樓。

Sample Input

Sample001
3 2
1 2
3 4
5 6
7 8

Sample Output

Sample001
10