드래곤 미로 (스몰)

당신은 드래곤 왕국의 왕자다. 왕국의 힘이 바닥나기 직전이라 왕국과 백성을 구할 힘을 찾아야 한다. 오래된 전설은 그 힘이 드래곤 미로에 있다고 전한다. 드래곤 미로는 예고 없이 나타났다가 아무 경고도 없이 사라진다. 지금 미로의 위치를 알고 있으니 사라지기 전에 힘을 얻어야 한다.

드래곤 미로는 $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$이거나, 안전한 칸에 들어 있는 힘의 양을 뜻하는 양의 정수다.

제한

• $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$
• 한 칸에 들어 있는 힘은 $10\,000$을 넘지 않는다.
• 입구 칸과 출구 칸은 서로 다르며 둘 다 안전한 칸이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 입구에서 출구까지 갈 수 있으면 $y$는 걸음 수가 가장 적은 경로로 이동하면서 얻을 수 있는 힘의 최댓값이다. 갈 수 없으면 $y$는 Mission Impossible. 이다.

채점은 정확히 일치하는지를 본다. 마지막 마침표가 빠진 Mission Impossible 이나 소문자로 쓴 mission impossible. 은 오답으로 처리된다.