Lumbo Jumbo

In Lala land, young Lumbo and his older brother Jumbo used to play a game they loved. The original game went like this. Jumbo picks a number $N$ and draws a $3 \times N$ grid on the floor, marking some cells as important. A cell is written $(i, j)$, where $i$ is the row number (row 1 is the top row) and $j$ is the column number (column 1 is the leftmost column). The grid has 3 rows and $N$ columns. Jumbo then asks Lumbo to jump on the grid cells with one leg, following these rules:

1. Lumbo can start from any cell he chooses.
2. Every important cell must be visited at least once.
3. Lumbo can jump from one cell to another only if the two cells are adjacent. Two cells are adjacent if they share at least one edge.
4. Lumbo may visit non-important cells as many times as he wants. Otherwise the game could be impossible.

One day Jumbo decided the game was too easy, so he added a new rule:

5. Jumbo assigns a cost to each edge between two adjacent cells. To cross an edge, Lumbo pays its cost. Once Lumbo has paid for an edge, he can use it as many times as he wants without paying again.

Jumbo asks Lumbo to jump again under all the rules above, visiting each important cell at least once, and this time to minimize the total cost.

Lumbo tried several jumps but is not sure whether any of them is the cheapest. Help him compute the minimum cost.

The first line contains a single integer $T$, the number of test cases ($1 \le T \le 100$).

Each test case starts with a line containing two integers $N$ and $P$. $N$ is the number of columns ($1 \le N \le 10,000$), and $P$ is the number of important cells ($1 \le P \le 100$).

The next 3 lines each contain $N-1$ integers. The first line gives the costs of the vertical edges in row 1, that is, between $(1, 1)$ and $(1, 2)$, up to between $(1, N-1)$ and $(1, N)$. The second and third lines give the same for rows 2 and 3.

The next 2 lines each contain $N$ integers. The first line gives the cost of the edge between $(1, c)$ and $(2, c)$ for each column $c$. The second line gives the cost of the edge between $(2, c)$ and $(3, c)$ for each column $c$.

Every edge cost is between 0 and 100 inclusive ($0 \le$ edge cost $\le 100$).

The last $P$ lines each contain two integers $i$ and $j$, the row and column of an important cell ($1 \le i \le 3$, $1 \le j \le N$).

For each test case, print one line with the minimum cost Lumbo must pay to visit every important cell at least once.

The figure below explains the second test case.