동굴 탈출

Raven 씨는 N행 M열 행렬 모양의 동굴에 갇혀 있습니다. 행은 위에서 아래로 1부터 N까지, 열은 왼쪽에서 오른쪽으로 1부터 M까지 번호가 매겨져 있습니다. i행 j열의 칸은 (i, j)로 나타냅니다. Raven 씨는 (SR, SC) 칸에 있고, 동굴의 출구는 (TR, TC) 칸에 있습니다.

일부 칸에는 장애물이 있습니다. Raven 씨는 장애물이 있는 칸에 들어갈 수 없습니다. 다른 칸에는 함정이 있습니다. Raven 씨가 함정이 있는 칸에 처음 들어갈 때마다 함정의 세기만큼 에너지를 써야 합니다. 에너지가 부족하면 그 칸에 들어갈 수 없습니다. 또 다른 칸에는 물약이 있습니다. Raven 씨가 물약이 있는 칸에 처음 들어가면 물약의 세기만큼 에너지를 얻습니다.

Raven 씨는 처음에 E의 에너지를 가지고 있습니다. 변을 공유하는 칸으로만 이동할 수 있습니다(꼭짓점만 맞닿은 칸은 불가능합니다). 출구 칸에서는 동굴을 나가지 않고 계속 탐험할 수도 있습니다. 출구에 도달할 수 있다면, Raven 씨가 동굴을 나갈 때 가질 수 있는 에너지의 최댓값을 구하세요.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어집니다. 이어서 T개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 위에서 설명한 정수 일곱 개 N, M, E, SR, SC, TR, TC가 한 줄에 주어집니다. 다음 N줄은 동굴의 각 행을 나타냅니다. i번째 줄에는 M개의 정수 Vij가 주어지며, j번째 정수는 i행 j열 칸의 상태입니다. Vij는 다음 중 하나입니다.

• 0: 빈 칸.
• -100000: 장애물이 있는 칸.
• -99999 이상 -1 이하의 정수: 세기가 -Vij인 함정.
• 1 이상 99999 이하의 정수: 세기가 Vij인 물약.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력합니다. x는 테스트 케이스 번호(1부터 시작)이고, y는 Raven 씨가 출구에 도달했을 때 가질 수 있는 에너지의 최댓값입니다. 출구에 도달할 수 없다면 -1을 출력합니다.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 100.
• 1 ≤ M ≤ 100.
• 0 ≤ E ≤ 100000.
• 1 ≤ SR ≤ N.
• 1 ≤ SC ≤ M.
• 1 ≤ TR ≤ N.
• 1 ≤ TC ≤ M.
• (SR, SC) ≠ (TR, TC).
• 모든 i, j에 대해 -100000 ≤ Vij < 100000.
• -100000 < Vij < 0인 칸은 최대 15개입니다(함정은 최대 15개).
• VSRSC = 0 (Raven 씨의 시작 칸은 빈 칸입니다).
• VTRTC = 0 (출구 칸은 빈 칸입니다).

예제 1에서 Raven 씨는 출구에 도달할 수 없습니다.

예제 2의 동굴은 아래 그림과 같습니다.

• 양의 정수 x가 적힌 칸은 세기가 x인 물약입니다.
• 음의 정수 y가 적힌 칸은 세기가 -y인 함정입니다.
• Raven 씨의 시작 위치는 "You are here" 표시가 있는 칸입니다.

최대 에너지로 출구에 도달하는 방법 중 하나는 다음과 같습니다.

• 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으로 출구를 나갑니다.

이 경우는 Small 데이터셋에는 나오지 않습니다.