Cave Escape

Mr. Raven is stuck in a cave represented by a matrix of N rows and M columns. Rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to M from left to right. The cell at the i-th row and the j-th column is denoted by (i, j). Mr. Raven is at the cell (SR, SC), and the exit of the cave is at the cell (TR, TC).

Some cells contain obstacles. Mr. Raven cannot step into a cell with an obstacle. Other cells contain traps. The first time Mr. Raven enters a cell with a trap, he must spend energy equal to the strength of the trap. If he has less energy than needed, he cannot enter that cell. Some other cells contain potions. The first time Mr. Raven enters a cell with a potion, he gains energy equal to the strength of the potion.

Mr. Raven starts with E energy points. He can move between cells that share an edge (not just a corner). On the exit cell, he can choose not to leave the cave and keep exploring. Find the maximum number of energy points Mr. Raven can have when he exits the cave, if it is possible to reach the exit.

The first line of the input gives the number of test cases, T. Each of the next T test cases consists of one line with seven integers N, M, E, SR, SC, TR and TC as described above. The i-th of the next N lines describes the i-th row of the cave. Each line has M integers Vij, where the j-th integer is the cell in the j-th column of the i-th row. Each Vij is one of the following:

• 0: an empty cell.
• -100000: a cell with an obstacle.
• An integer from -99999 to -1: a trap with strength -Vij.
• An integer from 1 to 99999: a potion with strength Vij.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum energy points Mr. Raven can have when he reaches the exit. If he cannot reach the exit, output -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).
• -100000 ≤ Vij < 100000, for all i, j.
• At most 15 cells have -100000 < Vij < 0. (There are at most 15 traps.)
• VSRSC = 0. (Mr. Raven's initial position is an empty cell.)
• VTRTC = 0. (The exit cell is empty.)

In Sample Case #1, it is not possible for Mr. Raven to reach the exit.

In Sample Case #2, the cave is as shown in the following image.

• A cell with a positive integer x is a potion with strength x.
• A cell with a negative integer y is a trap with strength -y.
• Mr. Raven's initial position is the cell marked "You are here".

One optimal way to reach the exit with maximum energy is:

• Start with 250 energy.
• Go to and destroy the trap at (7, 3). 150 energy remaining.
• Collect the three potions at (6, 6), (6, 7) and (7, 6). 300 energy remaining.
• Go to and destroy the trap at (5, 7). 200 energy remaining.
• Collect the potion at (4, 6). 450 energy remaining.
• Go to and destroy the trap at (5, 2). 250 energy remaining.
• Collect the potion at (3, 2). 350 energy remaining.
• Go to and destroy the trap at (3, 3). 50 energy remaining.
• Collect the potion at (4, 4). 550 energy remaining.
• Go to and destroy the trap at (3, 6) and exit with 250 energy remaining.

This case will not appear in the Small dataset.