동굴 탈출

Mr. Raven은 N개의 행과 M개의 열로 이루어진 행렬로 표현되는 동굴에 갇혀 있다. 행은 위에서 아래로 1부터 N까지 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 1부터 M까지 번호가 매겨진다. i번째 행과 j번째 열의 칸을 (i, j)로 나타낸다. 현재 Mr. Raven은 ($S_{R}$, $S_{C}$) 칸에 있으며, 동굴의 출구는 ($T_{R}$, $T_{C}$) 칸에 있다.

동굴의 일부 칸에는 장애물이 있을 수 있다. Mr. Raven은 장애물이 있는 칸에 들어갈 수 없다. 다른 칸에는 함정이 있을 수 있다. Mr. Raven이 함정이 있는 칸에 처음 들어갈 때는 함정의 위력과 같은 수의 에너지 포인트를 소모해야 한다. 필요한 에너지 포인트보다 적게 가지고 있다면 그 칸에 들어갈 수 없다. 또한, 또 다른 일부 칸에는 물약이 있을 수 있다. Mr. Raven이 물약이 있는 칸에 처음 들어갈 때는 물약의 효력과 같은 수의 에너지 포인트를 얻는다.

Mr. Raven은 처음에 E 에너지 포인트를 가지고 있다. 그는 모서리만이 아니라 변을 공유하는 칸 사이를 이동할 수 있다. Mr. Raven은 출구 칸에서도 원한다면 동굴을 나가지 않고 계속 탐험할 수 있다. 동굴을 나가는 것이 가능하다면, 그가 동굴을 나갈 때 가질 수 있는 에너지 포인트의 최댓값을 구하도록 도와주자.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 120초. 메모리 제한: 1 GB. 1 ≤ N ≤ 100. 1 ≤ M ≤ 100. 0 ≤ E ≤ 100000. 1 ≤ $S_{R}$ ≤ N. 1 ≤ $S_{C}$ ≤ M. 1 ≤ $T_{R}$ ≤ N. 1 ≤ $T_{C}$ ≤ M. ($S_{R}$, $S_{C}$) ≠ ($T_{R}$, $T_{C}$). 모든 i, j에 대해 -100000 ≤ $V_{ij}$ < 100000. 최대 15개의 칸이 -100000 < $V_{ij}$ < 0를 만족한다. (함정은 최대 15개이다.) V_{$S_{R}$ $S_{C}$} = 0. (Mr. Raven의 초기 위치는 빈 칸이다.) V_{$T_{R}$ $T_{C}$} = 0. (출구가 있는 칸은 빈 칸이다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

$V_{ij}$ > 0인 칸은 없다. (동굴에 물약이 없다.)

큰 데이터 세트 (테스트 세트 2 - 비공개)

추가 제약 조건은 없다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 일곱 정수 N, M, E, $S_{R}$, $S_{C}$, $T_{R}$, $T_{C}$가 있는 한 줄로 구성된다. 이어지는 N개 줄 중 i번째 줄은 동굴의 i번째 행을 나타낸다. 각 줄은 M개의 정수 $V_{ij}$로 구성되며, 이 중 j번째 정수는 i번째 행의 j번째 열에 있는 칸을 나타낸다. 각 $V_{ij}$는 다음 중 하나일 수 있다.

• 0: 빈 칸을 나타낸다.

• -100000: 장애물이 있는 칸을 나타낸다.

• -99999 이상 -1 이하의 정수: 위력이 -$V_{ij}$인 함정을 나타낸다.

• 1 이상 99999 이하의 정수: 효력이 $V_{ij}$인 물약을 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 Mr. Raven이 동굴의 출구에 도달했을 때 가질 수 있는 에너지 포인트의 최댓값이다. Mr. Raven이 출구에 도달할 수 없다면 -1를 출력한다.

예제 케이스 #1에서는 Mr. Raven이 출구에 도달할 수 없다.

예제 케이스 #2에서는 함정도 물약도 없다. 따라서 Mr. Raven은 출구에 도달할 수 있으며, 어떤 경로를 따르더라도 에너지는 변하지 않는다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 동굴은 다음 그림과 같으며,

• 양의 정수 x가 있는 칸은 효력이 x인 물약을 나타낸다.

• 음의 정수 y가 있는 칸은 위력이 -y인 함정을 나타낸다.

• Mr. Raven의 초기 위치는 "현재 위치"라는 문구가 있는 칸이다.

이 경우, 최대 에너지 포인트를 가지고 출구에 도달하는 최적의 방법 중 하나는 다음과 같다.

• 250 에너지 포인트를 가지고 시작한다.

• (7, 3) 칸으로 가서 함정을 파괴한다. 에너지 포인트가 150 남는다.

• (6, 6), (6, 7), (7, 6) 위치에 있는 세 물약을 모두 수집한다. 에너지 포인트가 300 남는다.

• (5, 7) 칸으로 가서 함정을 파괴한다. 에너지 포인트가 200 남는다.

• (4, 6) 칸에서 물약을 수집한다. 에너지 포인트가 450 남는다.

• (5, 2) 칸으로 가서 함정을 파괴한다. 에너지 포인트가 250 남는다.

• (3, 2) 칸에서 물약을 수집한다. 에너지 포인트가 350 남는다.

• (3, 3) 칸으로 가서 함정을 파괴한다. 에너지 포인트가 50 남는다.

• (4, 4) 칸에서 물약을 수집한다. 에너지 포인트가 550 남는다.

• (3, 6) 칸으로 가서 함정을 파괴하고, 250 에너지 포인트가 남은 상태로 나간다.