Problem F

Liftless EME

Input: standard input

Output: standard output

Time Limit: 2 seconds

Memory Limit: 32 MB

The EME building has grown taller and taller from the year 2002 to 2020. But the number of lifts has remained constant. As a result, it has become a great problem for the students to reach their classes in time. Especially the contestants of ACM Preparation Contest are suffering very much. Their contest starts at exactly 2:00pm on every Tuesday and at that time, the lifts and the stairs are packed with lab-going students.

So the contestants decided to make some shortcut path to the ACM Lab. They secretly made some holes through the roofs of their classrooms and placed a ladder in each hole, so that they can move from one room of a floor to a room in the next floor without pushing the crowd.

This made a new problem for them: they have so many holes and some of the shortcut paths take much more time to traverse.

You are to find out the path from the ground floor (0-th floor) to the (n-1)-th floor that can be reached in shortest possible time. The contestants never climb down a ladder (except when the contest is over).

Input

Input consists of several test cases.

Each case consists of the case name (consisting of up to 12 alphanumeric characters) in a line followed by a line with two integers n (the number of roofs in the EME building, except the topmost roof) and m (number of holes through each roof). The next m(n-1) lines each contains m integers. The j-th integer in the(km+i)-th line (where 0 £ k < n-1 < 120, 1 £ i, j £ m £ 15) is the time (in minutes) needed to walk from the i-th hole through the roof of k-th floor (i.e. the i-th hole through the floor of (k+1)-th floor) to the ladder at the j-th hole through the roof of (k+1)-th floor. It takes 2 minutes to climb each ladder, but you shouldn't consider the time needed by the ladders at the ground floor.

Input in terminated by end of file.

Output

For each data set, print 2 lines: The first line is the case name and the second line is the minimum time needed to reach the (n-1)-th floor.

Sample Input

Sample001
3 2
1 2
3 4
5 6
7 8

Sample Output

Sample001
10

Mustaq Ahmed