Mathison and the teleportation game

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Mathison and Chef are playing a new teleportation game. This game is played on a R×C board where each cell contains some value. A cell at xth row and yth column is denoted by (x,y). 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 telpair.
A player is given N telpairs. Each telpair 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 telpair 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 all) of the telpairs given.
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 telpairs.
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 telpairs. The first one will contain N integers, the xcomponent of each telpair. The second one will contain N integers, the ycomponent of each telpair.
Next, there will be R lines, each containing C 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 ≤ T ≤ 100
 1 ≤ R, C ≤ 1000
 1 ≤ N ≤ 9
 0 ≤ Sx < R
 0 ≤ Sy < C
 0 ≤ dx ≤ R
 0 ≤ dy ≤ C
 The value of a cell is a natural number between 1 and 1,000,000 (i.e. 10^{6}).
 You are allowed to visit a cell multiple times!
 It's not allowed to go outside the board!
 If a cell is visited more than once, its value should be taken into account every single time!
 You don't have to use all telpairs (but you may want to).
 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 values of the cells in the path.
 Note: You may want to use faster reading methods!
 Note: The time limits (TLs) are given per input file!
Subtaks
Subtask #1 (15 points):
 T ≤ 100
 R, C ≤ 10
 N ≤ 4
 TL = 1s
Subtask #2 (25 points):
 T ≤ 25
 R, C ≤ 100
 N ≤ 8
 TL = 1.5s
Subtask #3 (30 points):
 T ≤ 5
 R, C ≤ 1000
 N ≤ 8
 TL = 2s
Subtask #4 (30 points):
 T ≤ 5
 R, C ≤ 1000
 N ≤ 9
 TL = 2.5s
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 Output: 188 24 3
Explanation
First test Mathison starts at (2, 2). Mathison has two telpairs (2, 1) and (1, 2). The following path (i.e. bolded numbers) generates the maximum value: (2, 2) → (4, 1) → (3, 3) Second test Mathison starts at (0, 0). Mathison has two telpairs (1, 1) and (1, 1). The following path (i.e. bolded numbers) generates the maximum value: (0, 0) → (1, 1) → (0, 0) Third test Mathison starts at (1, 1). Mathison has one telpair, (2, 2). He can't use the telpair so the answer is 3 (the value of the starting cell).
Author:  alexvaleanu 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/MATTEG 
Tags  alexvaleanu, bitmasking, dynamicprogramming, ltime51, medium 
Date Added:  23082017 
Time Limit:  1  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 