Apocalypse Soon (Large)

The political balance of the world has finally collapsed and every nation has declared war on every other nation. Industrial centers are already gone, so the only attack a nation has left is to hurl conscripted soldiers at the nations beside it. That limits every nation to attacking its immediate neighbors.

The world is a grid with $R$ rows and $C$ columns. Rows are numbered 1 in the far north to $R$ in the far south, and columns are numbered 1 in the far west to $C$ in the far east. Each nation occupies one square of the grid, so it touches at most 4 other nations.

Every nation's strength is known to everyone. The nations other than yours have no concept of strategy, so each morning a nation picks the living neighbor with the largest strength. A tie goes to the northernmost of those neighbors, and then to the westernmost. It sends an army whose power equals its own strength $S$ that morning, and at the end of the day the target's strength drops by $S$. A nation whose strength reaches 0 is destroyed. A destroyed nation neither attacks nor is attacked, and it is not a candidate when a strongest neighbor is picked. A nation with no living neighbor does nothing that day.

All attacks happen at the same time. An army's power comes from the strength its nation had that morning, whether or not that nation is attacked the same day.

Your nation sits in column $c$, row $r$, and it listens to your advice, so it does not follow that crazy strategy. Each day you may attack any one living neighbor, or do nothing at all. You cannot attack two neighbors on the same day, and you cannot send an army weaker than your strength that morning.

Days are numbered 1, 2, 3, and so on. You survive day $d$ if your strength is still above 0 after every attack of day $d$ has been applied. Find the largest $D$ such that you can survive day 1 through day $D$. If you can outlast all of your neighbors and stay alive without limit, report that instead.

The first line of input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains four integers $C$, $R$, $c$ and $r$. The next $R$ lines each contain $C$ integers, giving the starting strength $S_{c_i, r_i}$ of the nation in column $c_i$ and row $r_i$. That value may be 0, which means the nation has already been destroyed. Your nation's starting strength is not 0.

Limits

• $1 \le T \le 100$
• $1 \le c \le C \le 50$
• $1 \le r \le R \le 50$
• $0 \le S_{c_i, r_i} \le 1000$

For each test case, print one line containing Case #A: followed by the answer below. $A$ is the test case number, starting from 1.

• B day(s), where $B$ is the largest number of days you can survive. $B$ may be 0.
• forever, if you can stay alive without limit.