你在游戏《戴森球计划》中来到了一个新的星球，并放下了n个生产设备。虽然星球是个球形，但是可以将其抽象成一个二维平面，其中第i个生产设备的坐标为x_i,y_i。

你想让每个生产设备都通上电。第i个设备能通上电，当且仅当能满足以下一个条件：

- 为第i个设备建造一个火力发电厂（或者微型聚变发电站或者人造恒星），这将花费c_i元；

- 选择另一个**有电的**设备j(j\neq i)，在设备i和设备j之间拉起电线（其实在游戏里是电力感应塔无线输电塔或者卫星配电站）。设备i和设备j之间安装电线的价格是每公里k_i+k_j元，其中k_i,k_j分别是设备i和设备j的用电量。电线只能走基本方向（北、南、东、西）。电线可以相互交叉但互不影响。综上，如果设备i和设备j通过电线连接，则电线的长度为|x_i−x_j|+|y_i−y_j|公里。因此，在设备i和设备j之间拉电线的花费是(k_i+k_j)(|x_i−x_j|+|y_i−y_j|)。

你想用尽可能少的钱来让每个电线都能通上电。你需要输出这一最小花费。

注意：即使当i\neq j时，(x_i,y_i)=(x_j,y_j)也是可能的。

第一行有一个整数id(1\leq id \leq 20)，表示测试点编号。**你可以用这个信息来判断每个测试点的特殊性质（具体见数据范围与约定）**。

第二行有一个整数n，意义如题。

然后有n行，第i+2行有两个整数x_i和y_i，表示第i个设备的坐标。

紧接着一行n个整数，分别是c_1,c_2,\cdots,c_n。

最后一行n个整数，分别是k_1,k_2,\cdots,k_n。

输出一个整数，表示让所有设备通上电的最小花费。

|测试点编号id |n |c_i |x_i,y_i,k_i |

| ------ | ------ | ------ | ------ |

|1 \sim 4 |n \leq 100 |10^8 \leq c_i \leq 10^9 |k_i=1,x_i=1,1 \leq y_i\leq 10^6 |

|5 \sim 10 |n \leq 100 |10^8 \leq c_i \leq 10^9 |k_i=1,1 \leq x_i,y_i\leq 10^6 |

|11 \sim 14 |n \leq 2000 |10^8 \leq c_i \leq 10^9 |k_i=1,1 \leq x_i,y_i\leq 10^6 |

|15 \sim 20 |n \leq 2000 |1 \leq c_i \leq 10^9 |1\leq k_i \leq 10^3,1 \leq x_i,y_i\leq 10^6 |

## 样例解释

在样例1中，在第4个设备建设发电站，其他4个设备通过电线连向第4个设备。

在样例2中，在第2个设备建设发电站，另外两个设备通过电线连向第2个设备，总花费是2+10+15=27。