七九寺是南黑螺寺的新住神。她的第一份工作是这样的:
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$$$ 的任何最短路径。因此,如果 City $$$i$$$ 和 City $$$j$$$ 连接,电线的长度为 $$$|x_i - x_j| + |y_i - y_j|$$$ 公里。
七九寺希望花尽可能少的钱来做这份工作,因为据她说,世界上除了钱之外什么都没有。然而,她在五年级时就去世了,所以她不够聪明,无法做到这一点。因此,新的驻地神请求你的帮助。
因此,您必须向七九寺提供以下信息:向所有城市提供电力所需的最低日元金额、将在哪些城市建设发电站以及要建立的连接。
如果有多种方式选择城市和连接以获得最低建造价格,则打印其中任何一种。
输入
输入的第一行包含一个整数 $$$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$$$)。
输出
在第一行打印一个整数,表示所需的最低日元金额。
然后,打印一个整数 $$$v$$$ — 待建发电站的数量。
接下来,打印 $$$v$$$ 以空格分隔的整数,表示将建设电站的城市的索引。每个数字应从 $$$1$$$ 到 $$$n$$$ 且所有数字应成对不同。您可以按任意顺序打印数字。
之后,打印一个整数 $$$e$$$ — 要建立的连接数。
最后,打印 $$$e$$$ 整数对 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \ne b$$$),表示将在 City $$$a$$$ 和 City $$$b$$$ 之间建立连接。每个无序城市对最多应包含一次(对于每个 $$$(a, b)$$$ 不应再有 $$$(a, b)$$$ 或 $$$(b, a)$$$ 对)。您可以按任意顺序打印这些对。
如果有多种方式选择城市和连接以获得最低建造价格,则打印其中任何一种。
示例
输入 #1
3 2 3 1 1 3 2 3 2 3 3 2 3
输出 #1
8 3 1 2 3 0
输入 #2
3 2 1 1 2 3 3 23 2 23 3 2 3
输出 #2
27 1 2 2 1 2 2 3
注意
样本中给出的答案请参考下图(有电站的城市为绿色,其他城市为蓝色,电线为红色):
对于第一个示例,在所有城市建设发电站的成本为 $$$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日元。