163. Dancing With Numbers

Problem Statement:

Fillip is a professional dancer; he is very good at dancing that he invented his own dancing game. Unfortunately, he likes numbers too, therefor his game is full of dancing and full of numbers, he calls it "Dancing with the Numbers"

The game is very simple, there is a two dimensional dance floor divided into square cells, the dancer starts in the first cell and have to dance until he reach the final cell, in each dance move, he must move from his current cell to any adjacent cell (left, right, up or down) that he hasn't visited before. The problem is that each cell the dancer visits in his way, adds some points to his score, each cell has its own number of points. For this game the lower the score the better, you need to minimize your score.

Fillip needs your help to determine the lowest possible score for a specific dance floor.

Given N*M dancer floor and the number of points in each cell. For simplicity the starting cell will always be the cell (1, 1) and the final cell will be the cell (n, m).

You need to find the lowest possible score.

Input Format:

The first line contains the number of the test cases T (<=100). Each test case consists of many lines. The first line contains 2 numbers N M (1<=N, M<=100) as described in the problem statements, the next N lines, each contains exactly M positive integers representing the points in each cell (<=10^5).

Output Format:

For each test case print one line contains one integer representing the lowest possible score.

Sample Input:

1
3 3
1 3 4
1 2 4
1 2 3

Sample Output:

8