드래곤 미로 (라지)

당신은 드래곤 왕국의 왕자다. 왕국의 힘이 바닥나고 있어서, 백성을 구하려면 새 힘을 구해와야 한다. 옛 전설에 따르면 그 힘은 드래곤 미로라는 곳에 있다. 드래곤 미로는 예고 없이 아무 곳에나 나타났다가 갑자기 사라진다. 지금은 미로가 어디 있는지 알고 있으니, 사라지기 전에 힘을 가져와야 한다.

드래곤 미로는 $N \times M$ 칸으로 이루어진 직사각형이다. 왼쪽 위 칸이 $(0, 0)$, 오른쪽 아래 칸이 $(N-1, M-1)$이다. 각 칸은 한 번 들어가면 다시 빠져나올 수 없는 위험한 칸이거나, 일정한 양의 힘이 놓인 안전한 칸이다. 안전한 칸에 들어가면 그 칸의 힘을 자동으로 얻고, 같은 칸의 힘은 한 번만 얻는다. 한 번 움직일 때 상하좌우로 맞닿은 칸으로 한 칸 간다.

입구 칸과 출구 칸의 위치는 알고 있다. 두 칸은 서로 다르고 둘 다 안전한 칸이다. 미로가 사라지기 전에 빠져나오려면 입구에서 출구까지 최소 이동 횟수로 걸어야 한다. 그런 경로가 여러 개면 그중 얻는 힘의 합이 가장 큰 경로를 고른다. 입구 칸에 놓인 힘도 얻는다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에 미로의 크기를 나타내는 두 정수 $N$과 $M$이 주어진다. 둘째 줄에 네 정수 $en_x$, $en_y$, $ex_x$, $ex_y$가 주어진다. 입구 칸은 $(en_x, en_y)$이고 출구 칸은 $(ex_x, ex_y)$이다. 이어지는 $N$개의 줄에는 각각 $M$개의 수가 공백으로 구분되어 주어지고, 미로의 칸을 위에서 아래로 나타낸다. 각 수는 위험한 칸을 뜻하는 $-1$이거나, 그 칸에 놓인 힘의 양을 뜻하는 양의 정수다.

제한

• 한 칸에 놓인 힘의 양은 $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$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호다. 입구에서 출구까지 갈 수 있으면 $y$는 최소 이동 횟수로 걸었을 때 모을 수 있는 힘의 최대 합이다. 갈 수 없으면 $y$는 문자열 Mission Impossible.이다. 채점은 글자가 정확히 일치하는지만 보므로 mission impossible.이나 마침표가 빠진 Mission Impossible은 틀린 답으로 처리된다.