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).

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from collections import namedtuple

CurrentPosition = namedtuple('current_position', 'points, cell, pairs')

T = int(input())
for _ in range(T):
    R, C, N = map(int, input().split())
    Sx, Sy = map(int, input().split())
    tx = map(int, input().split())
    ty = map(int, input().split())
    tel_pairs = list(zip(tx, ty))
    board = []
    for _ in range(R):
        board += [[int(c) for c in input().split()]]
    
    def explore(p):
        next_pos = []
        for i, (dx, dy) in enumerate(p.pairs):
            sx, sy = p.cell
            new_pairs = p.pairs[:i]+p.pairs[i+1:]
            # case (+, +)
            px, py = sx + dx, sy + dy
            if px < R and py < C:
                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]
            # case (+, -)
            px, py = sx + dx, sy - dy
            if px < R and 0 <= py:
                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]
            # case (-, +)
            px, py = sx - dx, sy + dy
            if 0 <= px and py < C:
                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]
            # case (-, -)
            px, py = sx - dx, sy - dy
            if 0 <= px and 0 <= py:
                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]
        return next_pos
    
    pos = [CurrentPosition(board[Sx][Sy], (Sx, Sy), tel_pairs)]
    result = board[Sx][Sy]
    while pos:
        p = pos.pop(0)
        if p.pairs:
            pos += explore(p)
        else:
            result = max(result, p.points)
        
    print(result)