题目描述

X 县有 $n$ 座城市，编号从 $1$ 到 $n$。第 $i$ 座城市位于坐标 $(x_i, y_i)$，两座城市 $i,j$ 之间的电线长度定义为曼哈顿距离 $|x_i - x_j| + |y_i - y_j|$。

为了让所有城市通上电，你可以采取两种操作：

• 在第 $i$ 座城市建造一座发电站，花费 $c_i$；
• 在任意两座城市 $i,j$ 之间铺设电线，花费为 $(k_i + k_j) \cdot (|x_i - x_j| + |y_i - y_j|)$。

一座城市被“通电”是指：它本身有发电站，或者它通过电线（直接相连或经过若干座城市中转）与某座有发电站的城市连通。目标是用最小的花费让全部 $n$ 座城市都通电。如果存在多种最小花费方案，输出任意一种即可。

输入格式

从标准输入读入数据。

第一行一个整数 $n$（$1 \le n \le 2000$），表示城市数量。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i, y_i$（$1 \le x_i, y_i \le 10^6$），表示第 $i$ 座城市的坐标。

接下来一行 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），表示在第 $i$ 座城市建造发电站的花费。

最后一行 $n$ 个整数 $k_1, k_2, \dots, k_n$（$1 \le k_i \le 10^9$）。

输出格式

输出到标准输出。

第一行输出一个整数，表示为所有城市通电所需的最小花费。

第二行输出一个整数 $v$，表示建造发电站的城市数量。

第三行输出 $v$ 个整数，表示这些城市的编号，须在 $1$ 到 $n$ 之间且两两不同，顺序任意。

第四行输出一个整数 $e$，表示铺设的电线数量。

接下来 $e$ 行，每行两个整数 $a, b$（$1 \le a, b \le n$，$a \ne b$），表示在城市 $a$ 和城市 $b$ 之间铺设电线。每对无序城市最多出现一次（不应同时出现 $(a,b)$ 和 $(b,a)$）。$e$ 可以为 $0$，此时不输出任何电线行。

保证至少存在一种合法方案；若多种最小花费方案并存，输出任意一种。

样例 #1

3
1 1
1 2
2 1
5 5 5
1 1 1

9
1
1
2
1 2
1 3

样例解释 #1

在 1 号城市建站花费 $5$。连接 1–2 的电线长度为 $1$，花费 $(1+1)\cdot 1 = 2$；连接 1–3 同样花费 $2$。总花费 $5 + 2 + 2 = 9$。若三座城市都建站则需 $15$，因此 $9$ 是最小花费。

样例 #2

4
1 1
2 1
3 1
4 1
10 1 1 10
1 1 1 1

6
2
2 3
2
1 2
3 4

样例解释 #2

在 2、3 号城市建站，花费 $1 + 1 = 2$。再连接 1–2 与 3–4，各花费 $2$，总花费 $6$。只建一座发电站无法得到比这更小的花费。

样例 #3

5
10 10
10 11
10 12
11 10
9 10
1 100 100 100 100
1 1 1 1 1

9
1
1
4
1 2
1 4
1 5
2 3

样例解释 #3

在 1 号城市建站花费 $1$。连接 1–2、1–4、1–5 各花费 $2$，连接 2–3 花费 $2$，总花费 $9$。五座城市由此全部通电。

数据范围

对于所有数据：$1 \le n \le 2000$，$1 \le x_i, y_i \le 10^6$，$1 \le c_i, k_i \le 10^9$。允许不同城市坐标相同。

本题按测试点独立计分，满分 $100$ 分。下表按数据规模给出部分分档次（同一档次的测试点具有相同的附加约束）：

提示

坐标相同的多座城市之间电线长度为 $0$，铺设它们不增加花费；电线可以交叉，不影响费用。