CF1245D.Shichikuji and Power Grid

Shichikuji is the new resident deity of the South Black Snail Temple. Her first job is as follows:

There are $n$ new cities located in Prefecture X. Cities are numbered from $1$ to $n$. City $i$ is located $x_i$ km North of the shrine and $y_i$ km East of the shrine. It is possible that $(x_i, y_i) = (x_j, y_j)$ even when $i \ne j$.

Shichikuji must provide electricity to each city either by building a power station in that city, or by making a connection between that city and another one that already has electricity. So the City has electricity if it has a power station in it or it is connected to a City which has electricity by a direct connection or via a chain of connections.

• Building a power station in City $i$ will cost $c_i$ yen;
• Making a connection between City $i$ and City $j$ will cost $k_i + k_j$ yen per km of wire used for the connection. However, wires can only go the cardinal directions (North, South, East, West). Wires can cross each other. Each wire must have both of its endpoints in some cities. If City $i$ and City $j$ are connected by a wire, the wire will go through any shortest path from City $i$ to City $j$. Thus, the length of the wire if City $i$ and City $j$ are connected is $|x_i - x_j| + |y_i - y_j|$ km.

Shichikuji wants to do this job spending as little money as possible, since according to her, there isn't really anything else in the world other than money. However, she died when she was only in fifth grade so she is not smart enough for this. And thus, the new resident deity asks for your help.

And so, you have to provide Shichikuji with the following information: minimum amount of yen needed to provide electricity to all cities, the cities in which power stations will be built, and the connections to be made.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

志筑寺是南黑蜗牛神社新任的驻守神明。她的第一项任务如下：

在X县有 $n$ 座新建的城市，城市编号为 $1$ 至 $n$。城市 $i$ 位于神社以北 $x_i$ 千米、以东 $y_i$ 千米处。即使 $i \ne j$，也可能出现 $(x_i, y_i) = (x_j, y_j)$ 的情况。

志筑寺需为每座城市供电，方式有两种：一是在该城市建造一座发电站；二是在该城市与另一座已通电的城市之间架设连接线路。因此，当且仅当某城市自身建有发电站，或通过一条（直接或间接）线路链与某座已通电城市相连时，该城市才视为已通电。

• 在城市 $i$ 建造一座发电站的花费为 $c_i$ 日元；
• 在城市 $i$ 与城市 $j$ 之间架设连接线路的花费为 $(k_i + k_j)$ 日元/千米（按所用导线长度计费）。但导线只能沿正交方向（北、南、东、西）铺设；导线可以相互交叉；每条导线的两个端点必须均位于城市中。若城市 $i$ 与城市 $j$ 之间架设导线，则导线将沿二者之间的任意一条最短路径铺设。因此，若城市 $i$ 与城市 $j$ 相连，导线长度为 $|x_i - x_j| + |y_i - y_j|$ 千米。

志筑寺希望以最少的花费完成此项任务，因为在她看来，世上除了金钱别无他物。然而，她小学五年级便已去世，尚不足以独立解决此问题。因此，这位新任驻守神明向你求助。

你需要向志筑寺提供以下信息：为所有城市供电所需的最少日元金额、应建造发电站的城市列表，以及需架设的所有连接线路。

若存在多种方案可达到最小总花费，请输出其中任意一种即可。

First line of input contains a single integer $n$ ($1 \leq n \leq 2000$) — the number of cities.

Then, $n$ lines follow. The $i$-th line contains two space-separated integers $x_i$ ($1 \leq x_i \leq 10^6$) and $y_i$ ($1 \leq y_i \leq 10^6$) — the coordinates of the $i$-th city.

The next line contains $n$ space-separated integers $c_1, c_2, \dots, c_n$ ($1 \leq c_i \leq 10^9$) — the cost of building a power station in the $i$-th city.

The last line contains $n$ space-separated integers $k_1, k_2, \dots, k_n$ ($1 \leq k_i \leq 10^9$).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2000$）——表示城市的数量。

接下来是 $n$ 行。第 $i$ 行包含两个以空格分隔的整数 $x_i$（$1 \leq x_i \leq 10^6$）和 $y_i$（$1 \leq y_i \leq 10^6$）——表示第 $i$ 个城市的坐标。

下一行包含 $n$ 个以空格分隔的整数 $c_1, c_2, \dots, c_n$（$1 \leq c_i \leq 10^9$）——表示在第 $i$ 个城市建造发电站的成本。

最后一行包含 $n$ 个以空格分隔的整数 $k_1, k_2, \dots, k_n$（$1 \leq k_i \leq 10^9$）。

In the first line print a single integer, denoting the minimum amount of yen needed.

Then, print an integer $v$ — the number of power stations to be built.

Next, print $v$ space-separated integers, denoting the indices of cities in which a power station will be built. Each number should be from $1$ to $n$ and all numbers should be pairwise distinct. You can print the numbers in arbitrary order.

After that, print an integer $e$ — the number of connections to be made.

Finally, print $e$ pairs of integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), denoting that a connection between City $a$ and City $b$ will be made. Each unordered pair of cities should be included at most once (for each $(a, b)$ there should be no more $(a, b)$ or $(b, a)$ pairs). You can print the pairs in arbitrary order.

If there are multiple ways to choose the cities and the connections to obtain the construction of minimum price, then print any of them.

第一行输出一个整数，表示所需的最少日元金额。

然后，输出一个整数 $v$ —— 需要建设的发电站数量。

接下来，输出 $v$ 个用空格分隔的整数，表示将建设发电站的城市编号。每个编号应在 $1$ 到 $n$ 之间，且所有编号两两不同。你可以以任意顺序输出这些编号。

之后，输出一个整数 $e$ —— 需要建立的连接数量。

最后，输出 $e$ 对整数 $a$ 和 $b$（其中 $1 \le a, b \le n$，且 $a \ne b$），表示将在城市 $a$ 与城市 $b$ 之间建立一条连接。每对无序城市至多出现一次（即对于每一对 $(a, b)$，不应再出现 $(a, b)$ 或 $(b, a)$）。你可以以任意顺序输出这些数对。

如果存在多种选择城市和连接的方式，使得总建造费用最小，则输出其中任意一种即可。

For the answers given in the samples, refer to the following diagrams (cities with power stations are colored green, other cities are colored blue, and wires are colored red):

For the first example, the cost of building power stations in all cities is $3 + 2 + 3 = 8$. It can be shown that no configuration costs less than 8 yen.

For the second example, the cost of building a power station in City 2 is 2. The cost of connecting City 1 and City 2 is $2 \cdot (3 + 2) = 10$. The cost of connecting City 2 and City 3 is $3 \cdot (2 + 3) = 15$. Thus the total cost is $2 + 10 + 15 = 27$. It can be shown that no configuration costs less than 27 yen.

对于样例中给出的答案，请参考以下示意图（建有发电站的城市为绿色，其余城市为蓝色，电线为红色）：

对于第一个样例，所有城市均建造发电站的花费为 $3 + 2 + 3 = 8$。可以证明，不存在总花费低于 8 日元的方案。

对于第二个样例，在城市 2 建造发电站的花费为 2；连接城市 1 与城市 2 的花费为 $2 \cdot (3 + 2) = 10$；连接城市 2 与城市 3 的花费为 $3 \cdot (2 + 3) = 15$。因此总花费为 $2 + 10 + 15 = 27$。可以证明，不存在总花费低于 27 日元的方案。