드래곤 미로

당신은 Dragon Kingdom의 왕자이며, 왕국은 힘이 고갈될 위험에 처해 있다. 왕국과 백성을 구하려면 힘을 찾아야 한다. 오래된 전설에 따르면 힘은 Dragon Maze라고 알려진 장소에서 나온다. Dragon Maze는 아무런 예고 없이 어디선가 무작위로 나타났다가 경고 없이 갑자기 사라진다. 지금은 Dragon Maze가 어디에 있는지 알고 있으므로, 사라지기 전에 힘을 어느 정도 회수하는 것이 중요하다.

Dragon Maze는 직사각형 미로로, N x M개의 칸으로 이루어진 격자이다. 미로의 왼쪽 위 모서리 칸은 (0,0)이고 오른쪽 아래 모서리 칸은 (N-1, M-1)이다. 미로를 구성하는 각 칸은 들어가면 절대 빠져나올 수 없는 위험한 장소이거나, 일정량의 힘이 들어 있는 안전한 장소이다. 안전한 칸에 있는 힘은 그 칸에 들어가면 자동으로 수집되며, 단 한 번만 수집할 수 있다. 한 칸에서 시작하여 한 걸음으로 위/아래/왼쪽/오른쪽의 인접한 칸으로 이동할 수 있다.

이제 입구와 출구 칸의 위치를 알고 있으며, 두 칸은 서로 다르고 모두 안전한 칸이다. Dragon Maze가 사라지기 전에 빠져나가려면 가능한 한 적은 걸음으로 입구 칸에서 출구 칸까지 이동해야 한다. 선택할 수 있는 경로가 여러 개라면, 왕국을 구하기 위해 가능한 한 많은 힘을 수집할 수 있는 경로를 선택해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

각 칸에 들어 있는 힘의 양은 10,000을 초과하지 않는다. 1 ≤ T ≤ 30. 0 ≤ $en_{x}$, $ex_{x}$ < N. 0 ≤ $en_{y}$, $ex_{y}$ < M.

테스트 세트 1 - 공개

1 ≤ N, M ≤ 10.

테스트 세트 2 - 비공개

1 ≤ N, M ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 위에서 설명한 Dragon Maze의 크기를 나타내는 두 정수 N과 M이 들어 있는 줄로 시작한다. 각 테스트 케이스의 두 번째 줄에는 입구 칸 ($en_{x}$, $en_{y}$)과 출구 칸 ($ex_{x}$, $ex_{y}$)의 위치를 나타내는 네 정수 $en_{x}$, $en_{y}$, $ex_{x}$, $ex_{y}$가 주어진다. 그다음 N개의 줄이 주어지며, 각 줄에는 공백으로 구분된 M개의 수가 들어 있어 Dragon Maze의 N x M개 칸을 위에서 아래 순서로 나타낸다. 각 칸을 나타내는 수는 그 칸이 위험하다는 뜻의 -1이거나, 일정량의 힘이 들어 있는 안전한 칸이라는 뜻의 양의 정수이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. 입구에서 출구까지 이동할 수 있다면, y는 가능한 한 적은 걸음으로 이동하면서 수집할 수 있는 힘의 총량의 최댓값이어야 한다. 입구에서 출구까지 이동할 수 없다면, y는 문자열 "Mission Impossible."이어야 한다(따옴표는 명확성을 위한 것이다). 채점기는 정확히 일치하는 출력을 요구하므로, "mission impossible." 또는 맨 끝의 마침표가 빠진 "Mission Impossible"과 같은 다른 출력은 오답으로 판정된다는 점에 유의한다.