题目描述

有一个 $m \times m$ 的平面，给定 $n$ 个点，第 $i$ 个点位于平面的 $(x_i,y_i)$ 处，并有一个权值 $a_i$ 。定义一组方案为选择无序三元组 $(i,j,k)$ 满足 $i,j,k$ 互不相同且 $i < j < k$，该方案的权值为 $a_i+a_j+a_k$ 。我们称一组方案是合法的，当且仅当，我们取出 $(i,j),(j,k),(i,k)$ 这三对点对的曼哈顿距离，取出中位数 $\text{mid}$ ，若该数 $\text{mid}$ 为质数，且满足（$\text{mid} \bmod 20 = 3$ 或 $\text{mid} \leq 10$），则该方案是合法的。

统计在所有的 $n \times (n-1) \times (n-2)\times (6^{-1})$ 种方案中，所有合法方案的权值和。

点 $(x_0,y_0)$ 和点 $(x_1,y_1)$ 的曼哈顿距离为 $|x_0-x_1| + |y_0-y_1|$ 。

输入格式

本题开启多组测试。输入的第一行包含一个正整数 $T$ ，表示测试数据组数。对于每组测试数据：

输入的第一行包含两个正整数 $n,m$ ，分别表示点的数量和平面的大小。

接下来 $n$ 行，每行两个正整数 $x_i,y_i$ ，表示第 $i$ 个点的坐标为 $(x_i,y_i)$ 。

接下来一行 $n$ 个正整数，第 $i$ 个正整数 $a_i$ 表示点 $i$ 的权值。

输出格式

对于每组测试数据：输出一行一个整数，表示所有合法方案的权值和。

样例输入

2
3 5
1 1
2 2
3 3
1 2 3
10 30000
10177 27751
21553 29797
841 12385
23419 3661
20193 17395
18156 1566
5275 7233
29329 21553
12033 13381
14185 18697
1 2 3 4 5 6 7 8 9 10

样例输出

6
0

数据范围

对于 $100\%$ 的数据，保证 $1 \leq T \leq 5,1 \leq n \leq 8000 , 1 \leq m \leq 30000 , 1 \leq a_i \leq 10^{6} , 1 \leq x_i , y_i \leq m$ ，保证所有点在坐标范围内随机均匀生成，且任意不同编号的点的坐标不同。