在拉拉岛，小 Lumbo 和他的哥哥 Jumbo 过去常玩一个他们非常喜欢的游戏。最初，游戏规则如下：Jumbo 选择一个数字 $N$，然后在地板上画一个 $3 \times N$ 的网格，并标记出一些单元格作为重要单元格。网格中的单元格由一对坐标 $(i, j)$ 表示，其中 $i$ 是行号，且最上面的一行行号为 1；$j$ 是列号，且最左边的一列列号为 1。该网格共有 3 行和 $N$ 列。之后，Jumbo 要求 Lumbo 尝试用单脚在网格单元格上跳跃，并遵循以下规则：

1. 他可以从他选择的任何单元格开始。
2. 每个重要单元格必须至少被访问一次。
3. 他只能从一个单元格跳到另一个相邻的单元格。如果两个单元格至少共享一条边，则它们是相邻的。
4. 允许访问非重要单元格，次数不限。否则，游戏可能无法完成。

有一天，Jumbo 认为这个游戏太简单了，用他自己的话来说，昨天出生的孩子都能轻松完成，于是他决定增加一些新规则。因此，在上述规则之外，Jumbo 又增加了以下规则：

1. Jumbo 为网格中每两个相邻单元格之间的边分配了一个成本。为了跨越这条边，Lumbo 必须支付分配给该边的成本。为了方便起见，Jumbo 说，每当 Lumbo 支付了一条边的成本，他就可以多次使用该边而无需再次付费。

现在，和以前一样，他要求 Lumbo 用单脚在网格单元格上跳跃，使得他至少访问每个重要单元格一次，但这一次他必须最小化他所支付的总成本。Lumbo 尝试了几次跳跃，但他不确定其中任何一次是否达到了最小成本。Lumbo 觉得这对他来说太难了，所以他请求你帮助他计算最小成本。你能帮他战胜他的哥哥，证明他就是今天的孩子吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。

每个测试用例以包含两个整数的一行开始：

• $N$：网格的列数 ($1 \le N \le 10,000$)
• $P$：网格中重要单元格的数量 ($1 \le P \le 100$)

接下来的 3 行，每行将包含 $N-1$ 个空格分隔的整数，描述垂直分隔边的成本。第一行描述了分隔第 1 行单元格 $((1, 1), (1, 2), \dots, (1, N))$ 的边成本，第二行和第三行类似，分别描述了分隔第 2 行和第 3 行的边成本。

接下来的 2 行，每行将包含 $N$ 个空格分隔的整数，描述水平分隔边的成本。第一行描述了分隔第 1 列和第 2 列单元格 $(1, c)$ 和 $(2, c)$ 的边成本，第二行描述了分隔第 2 列和第 3 列单元格 $(2, c)$ 和 $(3, c)$ 的边成本 ($0 \le \text{edge\_costs} \le 100$)。

随后是 $P$ 行，每行包含 2 个空格分隔的整数：

• $i$：重要点的行号 ($1 \le i \le 3$)
• $j$：重要点的列号 ($1 \le j \le N$)

输出格式

对于每个测试用例，打印一行，包含 Lumbo 为了访问每个重要单元格至少一次所需要支付的最小跳跃成本。

样例

输入 1

2
3 4
11 28
1 62
94 89
31 15 64
76 57 33
1 2
1 1
1 3
2 3
4 3
13 21 32
11 6 70
23 14 15
16 23 31 17
34 13 11 9
1 1
3 4
1 4

输出 1

103
85

说明

这是第二个样例测试用例的解释：