Dragon Maze (Small)

You are the prince of the dragon kingdom, and the kingdom is about to run out of power. You have to find power to save the kingdom and its people. An old legend says that the power sits in a place called the Dragon Maze. The Dragon Maze appears without notice and disappears without warning. You know where it is right now, so you have to collect power before it is gone.

The Dragon Maze is a rectangular grid of $N \times M$ cells. The top left cell is $(0, 0)$ and the bottom right cell is $(N-1, M-1)$. Every cell is either a dangerous cell that you can never leave once you enter it, or a safe cell that holds a certain amount of power. The power in a safe cell is collected the moment you enter it, and each cell gives its power only once. In one step you move to a cell that is adjacent up, down, left, or right.

You already know the entrance cell and the exit cell. They are different cells and both of them are safe. To get out before the maze disappears, you have to walk from the entrance to the exit in as few steps as possible. When several paths use the fewest steps, take the one that collects the most power. The power in the entrance cell is collected as well.

For each test case, report the total power collected that way.

The first line contains the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integers $N$ and $M$, the size of the maze. The second line contains four integers $en_x$, $en_y$, $ex_x$, $ex_y$: the entrance cell is $(en_x, en_y)$ and the exit cell is $(ex_x, ex_y)$. The next $N$ lines describe the rows of the maze from top to bottom, each with $M$ numbers separated by spaces. Each number is either $-1$ for a dangerous cell, or a positive integer for the power held by a safe cell.

Limits

• $1 \le T \le 30$
• $1 \le N, M \le 10$
• $0 \le en_x, ex_x < N$
• $0 \le en_y, ex_y < M$
• The power in a cell does not exceed $10\,000$.
• The entrance cell and the exit cell are different, and both are safe.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1. If you can walk from the entrance to the exit, $y$ is the maximum power you can collect while taking the fewest possible steps. Otherwise $y$ is Mission Impossible.

The judge compares the output exactly. Mission Impossible without the trailing period, or mission impossible. in lower case, is judged wrong.