该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你在游戏《戴森球计划》中来到了一个新的星球，并放下了$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$。

输出格式

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

数据范围

输入样例 1

1
5
1 2
1 93
1 9
1 38
1 8
485167613 784430249 637393481 271981451 436803228
1 1 1 1 1

输出样例 1

271981633

输入样例 2

20
3
2 1
1 2
3 3
23 2 23
3 2 3

输出样例 2

27

样例解释

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