Dragon Maze (Large)

You are the prince of the Dragon Kingdom, and your kingdom is running out of power. To save your people you have to find new power. An old legend says the power sits in a place called the Dragon Maze. The Dragon Maze appears anywhere without notice and disappears just as suddenly. You know where it is right now, so you have to collect power before it vanishes.

The Dragon Maze is a rectangle of $N \times M$ cells. The top left cell is $(0, 0)$ and the bottom right cell is $(N-1, M-1)$. Each cell is either a dangerous cell you can never leave once you enter it, or a safe cell holding some amount of power. Entering a safe cell collects its power automatically, and the power of a cell is collected only once. One move takes you to a cell that shares an edge with your current cell, up, down, left, or right.

You know where the entrance cell and the exit cell are. They are different cells and both are safe. To get out before the maze disappears you have to walk from the entrance to the exit in as few moves as possible. When several such walks exist, take the one that collects the largest total power. The power in the entrance cell counts too.

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 contain $M$ numbers each, separated by spaces, describing the cells of the maze from top to bottom. Each number is either $-1$ for a dangerous cell, or a positive integer giving the amount of power in that safe cell.

Limits

• The power in one cell does not exceed $10000$.
• $1 \le T \le 30$
• $0 \le en_x, ex_x < N$
• $0 \le en_y, ex_y < M$
• $1 \le N, M \le 100$

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 total power you can collect while taking the fewest possible moves. If you cannot, $y$ is the string Mission Impossible.. The judge compares the output character by character, so mission impossible. or Mission Impossible without the trailing period is wrong.