Problem A

Consider a number maze represented as a two dimensional array of numbers comprehended between 0 and 9, as exemplified below. The maze can be traversed following any orthogonal direction (i.e., north, south, east and west). Considering that each cell represents a cost, then finding the minimum cost to travel the maze from one entry point to an exit point may pose you a reasonable challenge.

Your task is to find the minimum cost value to go from the top-left corner to the bottom-right corner of a given number maze of size NxM where 1 <= N, M <= 999. Note that the solution for the given example is 24.

The input file contains several mazes. The first input line contains a positive integer defining the number of mazes that follow. Each maze is defined by: one line with the number of rows, N; one line with the number of columns, M; and N lines, one per each row of the maze, containing the maze numbers separated by spaces.

For each maze, output one line with the required minimum value.

2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5

24
15