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