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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here\nfrom collections import namedtuple\n\nCurrentPosition = namedtuple('current_position', 'points, cell, pairs')\n\nT = int(input())\nfor _ in range(T):\n    R, C, N = map(int, input().split())\n    Sx, Sy = map(int, input().split())\n    tx = map(int, input().split())\n    ty = map(int, input().split())\n    tel_pairs = list(zip(tx, ty))\n    board = []\n    for _ in range(R):\n        board += [[int(c) for c in input().split()]]\n    \n    def explore(p):\n        next_pos = []\n        for i, (dx, dy) in enumerate(p.pairs):\n            sx, sy = p.cell\n            new_pairs = p.pairs[:i]+p.pairs[i+1:]\n            # case (+, +)\n            px, py = sx + dx, sy + dy\n            if px < R and py < C:\n                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]\n            # case (+, -)\n            px, py = sx + dx, sy - dy\n            if px < R and 0 <= py:\n                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]\n            # case (-, +)\n            px, py = sx - dx, sy + dy\n            if 0 <= px and py < C:\n                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]\n            # case (-, -)\n            px, py = sx - dx, sy - dy\n            if 0 <= px and 0 <= py:\n                next_pos += [CurrentPosition(p.points+board[px][py], (px, py), new_pairs)]\n        return next_pos\n    \n    pos = [CurrentPosition(board[Sx][Sy], (Sx, Sy), tel_pairs)]\n    result = board[Sx][Sy]\n    while pos:\n        p = pos.pop(0)\n        if p.pairs:\n            pos += explore(p)\n        else:\n            result = max(result, p.points)\n        \n    print(result)  \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 26017