Lumbo Jumbo

라라 랜드에 사는 어린 Lumbo와 형 Jumbo는 아주 좋아하던 게임을 즐겨 했다. 원래 게임은 이랬다. Jumbo가 수 $N$을 고르고, 바닥에 $3 \times N$ 격자를 그린 뒤 일부 칸을 중요한 칸으로 표시한다. 칸은 $(i, j)$로 적으며, $i$는 행 번호(가장 위 행이 1), $j$는 열 번호(가장 왼쪽 열이 1)이다. 격자는 3행 $N$열이다. 그 다음 Jumbo는 Lumbo에게 아래 규칙을 지키며 격자 칸 위를 한 발로 뛰라고 한다.

1. 아무 칸에서나 출발할 수 있다.
2. 모든 중요한 칸을 최소 한 번 방문해야 한다.
3. 두 칸이 변을 하나 이상 공유하면 인접한 것이고, 인접한 칸으로만 뛸 수 있다.
4. 중요하지 않은 칸은 원하는 만큼 몇 번이든 방문해도 된다. 그렇지 않으면 게임이 불가능할 수도 있다.

어느 날 Jumbo는 이 게임이 너무 쉽다고 여겨 새 규칙을 추가했다.

5. 인접한 두 칸 사이의 각 변마다 Jumbo가 비용을 정한다. 이 변을 건너려면 Lumbo는 그 변의 비용을 내야 한다. 한 번 비용을 낸 변은 다시 돈을 내지 않고 원하는 만큼 사용할 수 있다.

Jumbo는 위의 규칙을 모두 지키면서 중요한 칸을 각각 최소 한 번 방문하되, 지불하는 총비용을 최소로 하라고 요구한다. Lumbo는 여러 방법으로 뛰어 보았지만 그중 어느 것이 최소 비용인지 확신하지 못한다. Lumbo를 도와 최소 비용을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다($1 \le T \le 100$).

각 테스트 케이스는 정수 $N$과 $P$가 적힌 줄로 시작한다. $N$은 격자의 열 수($1 \le N \le 10,000$)이고, $P$는 중요한 칸의 수($1 \le P \le 100$)이다.

다음 3개 줄에는 각각 $N-1$개의 정수가 주어진다. 첫 줄은 1행의 세로 변 비용으로, $(1, 1)$과 $(1, 2)$ 사이부터 $(1, N-1)$과 $(1, N)$ 사이까지 차례로 주어진다. 둘째 줄과 셋째 줄도 같은 방식으로 2행과 3행에 해당한다.

다음 2개 줄에는 각각 $N$개의 정수가 주어진다. 첫 줄은 각 열 $c$에 대해 $(1, c)$와 $(2, c)$를 나누는 변의 비용이다. 둘째 줄은 각 열 $c$에 대해 $(2, c)$와 $(3, c)$를 나누는 변의 비용이다.

모든 변의 비용은 0 이상 100 이하이다($0 \le$ 변의 비용 $\le 100$).

마지막 $P$개 줄에는 중요한 칸의 행 번호 $i$와 열 번호 $j$가 각각 주어진다($1 \le i \le 3$, $1 \le j \le N$).

각 테스트 케이스마다, 중요한 칸을 모두 최소 한 번 방문하는 데 Lumbo가 내야 하는 최소 비용을 한 줄에 출력한다.

아래 그림은 두 번째 테스트 케이스를 설명한다.