Mathison and Chef are playing a new teleportation game. This game is played on a $R \times C$ board where each cell $(i, j)$ contains some value $V_{i, j}$. The purpose of this game is to collect a number of values by teleporting from one cell to another. A teleportation can be performed using a tel-pair.
A player is given $N$ tel-pairs. Each tel-pair can be used at most once and a player can use them in any order they like. Suppose a player is at cell $(a, b)$ and the tel-pair is $(dx, dy)$. Then, the player can reach in one teleportation any cell $(c, d)$ from $(a, b)$ such that $|a − c| = dx$ and $|b − d| = dy$.
It is Mathison’s turn next in the game to make a sequence of moves. He would like to know what is the highest value of a path of length at most $N+1$ that starts in $(Sx, Sy)$ and uses some (possibly none) of the tel-pairs given. The length of a path is equal to the number of cells in the path. The value of a path is equal to the sum of $V_{i, j}$ over all cells in the path.

-----Input-----
- The first line contains a single integer, $T$, the number of tests.
- Each test starts with three integers, $R$, $C$, and $N$, representing the number of rows, columns, and tel-pairs.
- The next line contains two integers, $Sx$, and $Sy$, representing the coordinates of the starting cell.
- The next two lines will contain the description of the tel-pairs, each containing $N$ space separated integers. The first will contain the $x$-component of each tel-pair, the second one will contain the y-component of each tel-pair.
- Finally, there will be $R$ lines, each containing $C$ space-separated integers, the description of the board.

-----Output-----
The output file will contain $T$ lines. Each line will contain the answer (i.e. the highest value of a path) to the corresponding test.

-----Constraints and notes-----
- $1 \leq T \leq 100$
- $1 \leq R, C \leq 1000$
- $1 \leq N \leq 9$
- $0 \leq Sx < R$
- $0 \leq Sy < C$
- $0 \leq dx \leq R$
- $0 \leq dy \leq C$
- $1 \leq V_{i, j} \leq 10^6$
- You are allowed to visit a cell multiple times in a path, and the value for the cell must be added each time you visit it.

-----Subtaks-----
Subtask #1 (15 points):
- $1 \leq T \leq 100$
- $1 \leq R, C \leq 10$
- $1 \leq N \leq 4$
Subtask #2 (25 points):
- $1 \leq T \leq 25$
- $1 \leq R, C \leq 100$
- $1 \leq N \leq 8$
Subtask #3 (30 points):
- $1 \leq T \leq 5$
- $1 \leq R, C \leq 1000$
- $1 \leq N \leq 8$
Subtask #4 (30 points):
- $1 \leq T \leq 5$
- $1 \leq R, C \leq 1000$
- $1 \leq N \leq 9$

-----Example Input-----
3
5 5 2
2 2
1 2
2 1
10 11 62 14 15
57 23 34 75 21
17 12 14 11 53
84 61 24 85 22
43 89 14 15 43
3 3 2
0 0
1 1
1 1
9 8 7
5 6 4
1 3 2
2 2 1
1 1
2
2
5 6
8 3

-----Example Output-----
188
24
3

-----Explanation-----
Test Case 1:
Mathison starts at $(2, 2)$.
Mathison has two tel-pairs $(2, 1)$ and $(1, 2)$.
The following path (i.e. bolded numbers) generates the maximum value: $(2, 2)$ → $(4, 1)$ → $(3, 3)$
Test Case 2:
Mathison starts at $(0, 0)$.
Mathison has two tel-pairs $(1, 1)$ and $(1, 1)$.
The following path (i.e. bolded numbers) generates the maximum value: $(0, 0)$ → $(1, 1)$ → $(0, 0)$
Test Case 3:
Mathison starts at $(1, 1)$.
Mathison has one tel-pair, $(2, 2)$.
He can't use the tel-pair so the answer is $3$ (the value of the starting cell).

见题面

见题面