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.


-----Input-----

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$).


-----Output-----

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.


-----Examples-----
Input
3
2 3
1 1
3 2
3 2 3
3 2 3

Output
8
3
1 2 3 
0

Input
3
2 1
1 2
3 3
23 2 23
3 2 3

Output
27
1
2 
2
1 2
2 3



-----Note-----

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):

[Image]

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.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Shortest paths

Greedy algorithms

Tree algorithms

Spanning trees


Solutions:
def main():
	n = int(input())
	xy = []
	for _ in range(n):
		xy.append(readIntArr())
	c = readIntArr()
	k = readIntArr()

	def getCost(i, j):
		if i == n:
			return c[j]
		if j == n:
			return c[i]
		(xi, yi) = xy[i]
		(xj, yj) = xy[j]
		return (k[i] + k[j]) * (abs(xi - xj) + abs(yi - yj))
	total = 0
	poweredCities = []
	connectedCities = []
	visited = [False] * (n + 1)
	costCheapest = [inf] * (n + 1)
	fromCheapest = [-1] * (n + 1)
	currCity = 0
	visited[currCity] = True
	for _ in range(n):
		for destination in range(n + 1):
			if currCity == destination:
				continue
			if visited[destination]:
				continue
			if getCost(currCity, destination) < costCheapest[destination]:
				costCheapest[destination] = getCost(currCity, destination)
				fromCheapest[destination] = currCity
		minCost = inf
		minCityFrom = -1
		minCityTo = -1
		for destination in range(n + 1):
			if currCity == destination:
				continue
			if visited[destination]:
				continue
			if costCheapest[destination] < minCost:
				minCost = costCheapest[destination]
				minCityFrom = fromCheapest[destination]
				minCityTo = destination
		assert minCityFrom != -1
		total += minCost
		visited[minCityTo] = True
		if minCityFrom == n:
			poweredCities.append(minCityTo + 1)
		elif minCityTo == n:
			poweredCities.append(minCityFrom + 1)
		else:
			connectedCities.append([minCityFrom + 1, minCityTo + 1])
		currCity = minCityTo
	print(total)
	print(len(poweredCities))
	oneLineArrayPrint(poweredCities)
	print(len(connectedCities))
	multiLineArrayOfArraysPrint(connectedCities)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
reader = (map(int, s.split()) for s in sys.stdin)
(n,) = next(reader)
locs = [tuple(next(reader)) for _ in range(n)]
cs = list(next(reader))
ks = list(next(reader))
totalCost = 0
stations = []
connections = []
connCosts = {i: cost for (i, cost) in enumerate(cs)}
connTo = [-1] * n
while connCosts:
	v = min(connCosts, key=connCosts.get)
	totalCost += connCosts[v]
	if connCosts[v] < cs[v]:
		to = connTo[v]
		connections.append((v, to))
	else:
		stations.append(v)
	connCosts.pop(v)
	for (to, cost) in connCosts.items():
		wire = ks[v] + ks[to]
		dist = abs(locs[v][0] - locs[to][0]) + abs(locs[v][1] - locs[to][1])
		newCost = wire * dist
		if connCosts[to] > newCost:
			connCosts[to] = newCost
			connTo[to] = v
myprint = sys.stdout.write
myprint(str(totalCost) + '\n')
myprint(str(len(stations)) + '\n')
[myprint(str(st + 1) + ' ') for st in stations]
myprint(str(len(connections)) + '\n')
[myprint(str(c1 + 1) + ' ' + str(c2 + 1) + '\n') for (c1, c2) in connections]


import os, sys
from io import BytesIO, IOBase

def prims(n, path, st, z, c, conn):
	(ans, where, visi) = (0, [z] * n, [0] * n)
	node = [path[j][z] for j in range(n)]
	visi[z] = 1
	while 1:
		(le, y, dig) = (float('inf'), -1, 0)
		for j in range(n):
			if visi[j]:
				continue
			if node[j] < c[j] and node[j] < le:
				(le, y, dig) = (node[j], j, 0)
			elif c[j] < node[j] and c[j] < le:
				(le, y, dig) = (c[j], j, 1)
		if le == float('inf'):
			return ans
		visi[y] = 1
		if not dig:
			conn.append((where[y] + 1, y + 1))
		else:
			st.append(y + 1)
		ans += le
		for (j, i) in enumerate(path[y]):
			if not visi[j] and i < node[j]:
				(node[j], where[j]) = (i, y)

def main():
	n = int(input())
	(x, y) = ([], [])
	for (a1, b1) in iter([map(int, input().split()) for _ in range(n)]):
		x.append(a1)
		y.append(b1)
	c = list(map(float, input().split()))
	k = list(map(float, input().split()))
	path = [[0] * n for _ in range(n)]
	for i in range(n):
		for j in range(i + 1, n):
			z = (k[i] + k[j]) * (abs(x[i] - x[j]) + abs(y[i] - y[j]))
			(path[i][j], path[j][i]) = (z, z)
	(z, ans, st, conn) = (c.index(min(c)), min(c), [], [])
	st.append(z + 1)
	ans += prims(n, path, st, z, c, conn)
	print(int(ans))
	print(len(st))
	print(*st)
	print(len(conn))
	for i in conn:
		print(*i)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import deque
from math import inf

def run_testcase():
	n = int(input())
	coords = [None] * (n + 1)
	for i in range(1, n + 1):
		coords[i] = [int(x) for x in input().split()]
	ci = [0] + [int(x) for x in input().split()]
	ki = [0] + [int(x) for x in input().split()]

	def cost(i, j):
		if i == j:
			return 0
		if i > j:
			(i, j) = (j, i)
		if i == 0:
			return ci[j]
		return (abs(coords[i][0] - coords[j][0]) + abs(coords[i][1] - coords[j][1])) * (ki[i] + ki[j])
	current_cost = 0
	tree = set([0])
	rest = set(range(1, n + 1))
	included = [True] + [False] * n
	connections = deque()
	connections_to_station = 0
	min_attach_cost = [(0, 0)] + [(cost(0, j), 0) for j in range(1, n + 1)]
	while len(tree) < n + 1:
		min_pair = (0, 0)
		min_cost = inf
		for node in rest:
			if min_attach_cost[node][0] < min_cost:
				min_pair = (min_attach_cost[node][1], node)
				min_cost = min_attach_cost[node][0]
		tree.add(min_pair[1])
		included[min_pair[1]] = True
		current_cost += min_cost
		rest.remove(min_pair[1])
		for node in rest:
			if cost(min_pair[1], node) < min_attach_cost[node][0]:
				min_attach_cost[node] = (cost(min_pair[1], node), min_pair[1])
		min_pair = tuple(sorted(min_pair))
		if min_pair[0] == 0:
			connections.appendleft(min_pair)
			connections_to_station += 1
		else:
			connections.append(min_pair)
	connections_list = list(connections)
	print(current_cost)
	print(connections_to_station)
	print(' '.join(map(lambda x: str(x[1]), connections_list[:connections_to_station])))
	print(len(connections_list) - connections_to_station)
	for i in range(connections_to_station, len(connections_list)):
		print(connections_list[i][0], connections_list[i][1])
run_testcase()


import math
n = int(input())
coor = []

def dis(x, y):
	return abs(x[0] - y[0]) + abs(y[1] - x[1])
for i in range(n):
	(u, v) = map(int, input().split())
	coor.append((u, v))
cost = list(map(int, input().split()))
k = list(map(int, input().split()))
d = {}
power_st = []
vis = [0] * n
connect = []
parent = [-1 for i in range(n)]
for i in range(n):
	d[i] = cost[i]
ans = 0
for i in range(n):
	m = min(d, key=d.get)
	if vis[m] == 0:
		power_st.append(m)
	else:
		connect.append([m, parent[m]])
	ans = ans + d[m]
	del d[m]
	for j in d.keys():
		t = dis(coor[m], coor[j]) * (k[m] + k[j])
		if t < d[j]:
			d[j] = t
			parent[j] = m
			vis[j] = 1
print(ans)
print(len(power_st))
for i in power_st:
	print(i + 1, end=' ')
print()
print(len(connect))
for i in connect:
	print(i[0] + 1, i[1] + 1)


def prim(n, adj):
	total_weight = 0
	(selected, min_e) = ([False] * n, [[float('inf'), -1] for _ in range(n)])
	mst_edges = []
	min_e[0][0] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not selected[j] and (v == -1 or min_e[j][0] < min_e[v][0]):
				v = j
		if min_e[v][0] == float('inf'):
			return (None, None)
		selected[v] = True
		total_weight += min_e[v][0]
		if min_e[v][1] != -1:
			mst_edges.append((v, min_e[v][1]))
		for to in range(n):
			if adj[v][to] < min_e[to][0]:
				min_e[to] = [adj[v][to], v]
	return (mst_edges, total_weight)

def main():
	n = int(input())
	xes = []
	yes = []
	for _ in range(n):
		(x, y) = readIntArr()
		xes.append(x)
		yes.append(y)
	c = readIntArr()
	k = readIntArr()

	def getCost(i, j):
		if i == n:
			return c[j]
		if j == n:
			return c[i]
		return (k[i] + k[j]) * (abs(xes[i] - xes[j]) + abs(yes[i] - yes[j]))
	adj = []
	for i in range(n + 1):
		arr = []
		for j in range(n + 1):
			if i == j:
				arr.append(inf)
			else:
				arr.append(getCost(i, j))
		adj.append(arr)
	(edges, totalCost) = prim(n + 1, adj)
	cityLinks = []
	powerStations = []
	for (i, j) in edges:
		if i == n:
			powerStations.append(j + 1)
		elif j == n:
			powerStations.append(i + 1)
		else:
			cityLinks.append([i + 1, j + 1])
	print(totalCost)
	print(len(powerStations))
	oneLineArrayPrint(powerStations)
	print(len(cityLinks))
	multiLineArrayOfArraysPrint(cityLinks)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import bisect
import functools
import math
import sys
from collections import defaultdict
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

def dist(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)

def main():
	n = ri()
	(x, y) = ([0] * n, [0] * n)
	for i in range(n):
		(x[i], y[i]) = rt()
	c = rl()
	k = rl()
	val = c.copy()
	used = [False] * n
	link = [-1] * n
	to_build = []
	for _ in range(n):
		min_index = -1
		min_val = math.inf
		for i in range(n):
			if not used[i] and val[i] < min_val:
				min_index = i
				min_val = val[i]
		used[min_index] = True
		if link[min_index] == -1:
			to_build.append(min_index + 1)
		for i in range(n):
			if not used[i]:
				to_link = (k[i] + k[min_index]) * dist(x[i], y[i], x[min_index], y[min_index])
				if to_link < val[i]:
					val[i] = to_link
					link[i] = min_index
	print(sum(val))
	print(len(to_build))
	print(*to_build)
	print(len([x for x in link if x > -1]))
	for i in range(n):
		if link[i] > -1:
			print(i + 1, link[i] + 1)

def __starting_point():
	main()
__starting_point()


N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
C = list(map(int, input().split()))
K = list(map(int, input().split()))
CC = [-1] * N
Ans = [-2] * N
total_cost = 0
for _ in range(N):
	mi = float('inf')
	for (i, (c, an)) in enumerate(zip(C, Ans)):
		if an == -2 and mi > c:
			mi = c
			ami = i
	total_cost += mi
	Ans[ami] = CC[ami]
	k1 = K[ami]
	(x1, y1) = XY[ami]
	for (i, (k2, (x2, y2))) in enumerate(zip(K, XY)):
		new_cost = (k1 + k2) * (abs(x1 - x2) + abs(y1 - y2))
		if C[i] > new_cost:
			C[i] = new_cost
			CC[i] = ami
print(total_cost)
cnt = Ans.count(-1)
print(cnt)
A = []
B = []
for (i, a) in enumerate(Ans, 1):
	if a == -1:
		A.append(i)
	else:
		B.append((i, a + 1))
print(' '.join(map(str, A)))
print(N - cnt)
for (a, b) in B:
	print(a, b)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def distgrid(a, b, k):
	return k * (abs(a[0] - b[0]) + abs(a[1] - b[1]))

def solve(case):
	n = int(inp())
	coor = []
	for i in range(n):
		(x, y) = sep()
		coor.append((x, y))
	c = lis()
	k = lis()
	vis = [False] * n
	wired = [-1] * n
	power = []
	connectn = []
	ans = 0
	for i in range(n):
		mini = 10 ** 10
		for j in range(n):
			if vis[j]:
				continue
			if c[j] < mini:
				mini = c[j]
				city = j
		ans += mini
		if wired[city] != -1:
			connectn.append((city, wired[city]))
		else:
			power.append(city)
		vis[city] = True
		for j in range(n):
			new = distgrid(coor[city], coor[j], k[city] + k[j])
			if new < c[j]:
				c[j] = new
				wired[j] = city
	print(ans)
	print(len(power))
	print(' '.join((str(power[i] + 1) for i in range(len(power)))))
	print(len(connectn))
	for i in range(len(connectn)):
		print(connectn[i][0] + 1, connectn[i][1] + 1)
testcase(1)


n = int(input())
pos = [[*map(int, input().split())] for i in range(n)]
(*c,) = map(int, input().split())
(*k,) = map(int, input().split())
used = [False for i in range(n)]
parent = [-1 for i in range(n)]
plants = []
connections = []
ans = 0
_n = n
while _n:
	_n -= 1
	(mn, u) = min([(ci, i) for (i, ci) in enumerate(c) if not used[i]])
	ans += mn
	used[u] = True
	if parent[u] == -1:
		plants.append(u)
	else:
		connections.append((min(parent[u], u), max(parent[u], u)))
	for i in range(n):
		con_cost = (k[u] + k[i]) * (abs(pos[u][0] - pos[i][0]) + abs(pos[u][1] - pos[i][1]))
		if con_cost < c[i]:
			c[i] = con_cost
			parent[i] = u
print(ans)
print(len(plants))
for p in sorted(plants):
	print(p + 1, end=' ')
print('')
print(len(connections))
for con in connections:
	print(con[0] + 1, con[1] + 1)


from math import *
c = int(input())
x = [0] * c
y = [0] * c
vu = [False] * c
for i in range(c):
	(x[i], y[i]) = [int(s) for s in input().split()]
prix = [int(s) for s in input().split()]
fil = [int(s) for s in input().split()]
anc = [-1] * c
pmin = prix.copy()
v = 0
pl = []
e = 0
ppl = []
tot = 0
for i in range(c):
	pmina = 100000000000000000000000
	for j in range(c):
		if not vu[j] and pmin[j] < pmina:
			pmini = j
			pmina = pmin[j]
	vu[pmini] = True
	tot += pmina
	if anc[pmini] == -1:
		v += 1
		pl.append(str(pmini + 1))
	else:
		e += 1
		ppl.append([str(pmini + 1), str(anc[pmini] + 1)])
	for j in range(c):
		if (abs(x[pmini] - x[j]) + abs(y[pmini] - y[j])) * (fil[pmini] + fil[j]) < pmin[j]:
			pmin[j] = (abs(x[pmini] - x[j]) + abs(y[pmini] - y[j])) * (fil[pmini] + fil[j])
			anc[j] = pmini
print(tot)
print(v)
print(' '.join(pl))
print(e)
for i in ppl:
	print(' '.join(i))


from sys import stdin, stdout
from collections import Counter

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
n = ip()
pos = [ai() for i in range(n)]
c = ai()
k = ai()
connections = []
plants = []
used = [False] * n
parent = [-1] * n
ans = 0
n_ = n
while n_:
	n_ -= 1
	(mn, u) = min([(ci, i) for (i, ci) in enumerate(c) if not used[i]])
	ans += mn
	used[u] = True
	if parent[u] == -1:
		plants.append(u)
	else:
		connections.append((min(parent[u], u), max(parent[u], u)))
	for i in range(n):
		con_cost = (k[u] + k[i]) * (abs(pos[u][0] - pos[i][0]) + abs(pos[u][1] - pos[i][1]))
		if con_cost < c[i]:
			c[i] = con_cost
			parent[i] = u
print(ans)
print(len(plants))
for i in sorted(plants):
	print(i + 1, end=' ')
print()
print(len(connections))
for i in connections:
	print(i[0] + 1, i[1] + 1)


import sys
reader = (map(int, s.split()) for s in sys.stdin)
(n,) = next(reader)
cities = [None]
for _ in range(n):
	(x, y) = next(reader)
	cities.append((x, y))
cs = [None] + list(next(reader))
ks = [None] + list(next(reader))
n += 1
g = [[None] * n for _ in range(n)]
for i in range(1, n):
	for j in range(i + 1, n):
		wire = ks[i] + ks[j]
		dist = abs(cities[i][0] - cities[j][0]) + abs(cities[i][1] - cities[j][1])
		g[i][j] = g[j][i] = wire * dist
for i in range(1, n):
	g[0][i] = g[i][0] = cs[i]
for i in range(n):
	g[i][i] = float('inf')
totalCost = 0
stations = []
connections = []
used = [False] * n
min_e = [float('inf')] * n
sel_e = [-1] * n
start = 0
min_e[start] = 0
for i in range(n):
	v = -1
	for j in range(n):
		if not used[j] and (v == -1 or min_e[j] < min_e[v]):
			v = j
	used[v] = True
	fromNode = sel_e[v]
	if not fromNode:
		totalCost += g[v][fromNode]
		stations.append(v)
	elif fromNode > 0:
		totalCost += g[v][fromNode]
		connections.append((v, fromNode))
	for to in range(n):
		if g[v][to] < min_e[to]:
			min_e[to] = g[v][to]
			sel_e[to] = v
myprint = sys.stdout.write
myprint(str(totalCost) + '\n')
myprint(str(len(stations)) + '\n')
[myprint(str(st) + ' ') for st in stations]
myprint(str(len(connections)) + '\n')
[myprint(str(c1) + ' ' + str(c2) + '\n') for (c1, c2) in connections]


import sys
input = sys.stdin.readline
n = int(input())
T = [tuple(map(int, input().split())) for i in range(n)]
C = list(map(int, input().split()))
K = list(map(int, input().split()))
import heapq
H = []
for (i, c) in enumerate(C):
	H.append((c, i + 1))
heapq.heapify(H)
ANS = 0
USE = [0] * (n + 1)
ANS1 = []
ANS2 = []
while H:
	x = heapq.heappop(H)
	if len(x) == 2:
		(cost, town) = x
		if USE[town] == 1:
			continue
		ANS += cost
		USE[town] = 1
		ANS1.append(town)
		(xt, yt) = T[town - 1]
		for i in range(n):
			if USE[i + 1] == 1:
				continue
			costp = (abs(T[i][0] - xt) + abs(T[i][1] - yt)) * (K[i] + K[town - 1])
			if costp < C[i]:
				C[i] = costp
				heapq.heappush(H, (costp, town, i + 1))
	else:
		(cost, town1, town2) = x
		if USE[town1] == 1 and USE[town2] == 1:
			continue
		ANS += cost
		USE[town2] = 1
		ANS2.append((town1, town2))
		(xt, yt) = T[town2 - 1]
		for i in range(n):
			if USE[i + 1] == 1:
				continue
			costp = (abs(T[i][0] - xt) + abs(T[i][1] - yt)) * (K[i] + K[town2 - 1])
			if costp < C[i]:
				C[i] = costp
				heapq.heappush(H, (costp, town2, i + 1))
sys.stdout.write(str(ANS) + '\n')
sys.stdout.write(str(len(ANS1)) + '\n')
print(*ANS1)
sys.stdout.write(str(len(ANS2)) + '\n')
for (x, y) in ANS2:
	sys.stdout.write(str(x) + ' ' + str(y) + '\n')


import sys
reader = (list(map(int, s.split())) for s in sys.stdin)
(n,) = next(reader)
xy = []
for _ in range(n):
	(x, y) = next(reader)
	xy.append([x, y])
c = list(next(reader))
k = list(next(reader))
graph = [[0 for _ in range(n + 1)] for _i in range(n + 1)]
for i in range(n):
	for j in range(i + 1, n):
		cost = (abs(xy[i][0] - xy[j][0]) + abs(xy[i][1] - xy[j][1])) * (k[i] + k[j])
		graph[i][j] = graph[j][i] = cost
	graph[n][i] = graph[i][n] = c[i]

def primMST():
	key = [1000000000000] * (n + 1)
	parent = [None] * (n + 1)
	key[0] = 0
	mstSet = [False] * (n + 1)
	parent[0] = -1
	for cout in range(n + 1):
		mn = 1000000000000
		for v in range(n + 1):
			if key[v] < mn and mstSet[v] == False:
				mn = key[v]
				min_index = v
		u = min_index
		mstSet[u] = True
		for v in range(n + 1):
			if graph[u][v] > 0 and mstSet[v] == False and (key[v] > graph[u][v]):
				key[v] = graph[u][v]
				parent[v] = u
	vss = 0
	cost = 0
	for i in range(1, n + 1):
		if parent[i] == n or i == n:
			vss += 1
		cost += graph[i][parent[i]]
	myprint = sys.stdout.write
	myprint(str(cost) + '\n')
	myprint(str(vss) + '\n')
	vs = [0] * vss
	es = [[]] * (n - vss)
	(k1, k2) = (0, 0)
	for i in range(1, n + 1):
		if parent[i] == n:
			vs[k1] = i + 1
			k1 += 1
		elif i == n:
			vs[k1] = parent[i] + 1
			k1 += 1
		else:
			es[k2] = [i + 1, parent[i] + 1]
			k2 += 1
	[myprint(str(st) + ' ') for st in vs]
	myprint('\n')
	myprint(str(len(es)) + '\n')
	[myprint(str(i[0]) + ' ' + str(i[1]) + '\n') for i in es]
primMST()


import sys
readline = sys.stdin.readline
rdw = lambda : readline().rstrip()
rdws = lambda : readline().split()
rdwl = lambda : list(readline().split())
rdi = lambda : int(readline())
rdis = lambda : list(map(int, readline().split()))
rdil = lambda : list(map(int, readline().split()))
rdilrows = lambda cnt: [rdil() for _ in range(cnt)]

def solve():
	res = 0
	bld = []
	wire = []
	n = rdi()
	cities = rdilrows(n)
	c = rdil()
	p = [-1 for i in range(n)]
	k = rdil()
	used = set()
	used.add(-1)
	for i in range(n):
		(cost, bst) = min([(c[i], i) for i in range(n) if i not in used])
		par = p[bst]
		used.add(bst)
		res += cost
		if par == -1:
			bld.append(bst + 1)
		else:
			wire.append((bst + 1, par + 1))
		for j in range(n):
			if j not in used:
				wcost = (k[bst] + k[j]) * (abs(cities[bst][0] - cities[j][0]) + abs(cities[bst][1] - cities[j][1]))
				if wcost < c[j]:
					c[j] = wcost
					p[j] = bst
	sys.stdout.write(f'{res}\n')
	sys.stdout.write(f'{len(bld)}\n')
	sys.stdout.write(f"{' '.join(map(str, bld))}\n")
	sys.stdout.write(f'{len(wire)}\n')
	for i in range(len(wire)):
		sys.stdout.write(f'{wire[i][0]} {wire[i][1]}\n')
tests = 1
for testnum in range(tests):
	solve()


def prim(matrix, inf=10 ** 18):
	n = len(matrix)
	costs = [inf] + [inf - 1] * (n - 1)
	nearest = [-1] * n
	current = 0
	total_cost = 0
	(build, connect) = ([], [])
	for _ in range(n - 1):
		min_cost = inf
		(src, dest) = (-1, -1)
		for i in range(n):
			if costs[i] == inf:
				continue
			if matrix[current][i] < costs[i]:
				costs[i] = matrix[current][i]
				nearest[i] = current
			if min_cost > costs[i]:
				min_cost = costs[i]
				(src, dest) = (nearest[i], i)
		total_cost += min_cost
		costs[dest] = inf
		if src == 0:
			build.append(dest)
		else:
			connect.append('%d %d' % (src, dest))
		current = dest
	return (build, connect, total_cost)
import sys
n = int(input())
pos = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
c_costs = list(map(int, input().split()))
k_costs = list(map(int, input().split()))
inf = 10 ** 18
matrix = [[inf] * (n + 1) for _ in range(n + 1)]
for i in range(n):
	for j in range(i + 1, n):
		matrix[i + 1][j + 1] = matrix[j + 1][i + 1] = (abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1])) * (k_costs[i] + k_costs[j])
	matrix[i + 1][0] = matrix[0][i + 1] = c_costs[i]
(build, connect, cost) = prim(matrix)
print(cost)
print(len(build))
print(*build)
print(len(connect))
if connect:
	print(*connect, sep='\n')


def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
n = int(input())
p = []
for i in range(n):
	p.append(list(map(int, input().split())))
c = list(map(int, input().split()))
k = list(map(int, input().split()))
st = []
ed = []
ans = 0
is_st = [1] * n
parent = [-1] * n
d = {i: c[i] for i in range(n)}
for i in range(n):
	m = min(d, key=d.get)
	if is_st[m]:
		st.append(m)
	else:
		ed.append([m, parent[m]])
	ans = ans + d[m]
	del d[m]
	for j in d.keys():
		t_cost = (k[m] + k[j]) * dist(p[m], p[j])
		if t_cost < d[j]:
			d[j] = t_cost
			parent[j] = m
			is_st[j] = 0
print(ans)
print(len(st))
for i in st:
	print(i + 1, end=' ')
print()
print(len(ed))
for i in ed:
	print(i[0] + 1, i[1] + 1)


def dis(x, y):
	return abs(x[0] - y[0]) + abs(x[1] - y[1])
n = int(input())
coor = []
for i in range(n):
	(x, y) = map(int, input().split())
	coor.append([x, y])
cost = list(map(int, input().split()))
k = list(map(int, input().split()))
d = {}
for i in range(n):
	d[i] = cost[i]
parent = [-1 for i in range(n + 1)]
visited = [0 for i in range(n + 1)]
m = 0
connect = []
power_set = []
(ans, t) = (0, 0)
for i in range(n):
	m = min(d, key=d.get)
	if visited[m] == 1:
		connect.append([m, parent[m]])
	else:
		power_set.append(m)
	ans += d[m]
	del d[m]
	for j in d.keys():
		t = dis(coor[j], coor[m]) * (k[j] + k[m])
		if t < d[j]:
			d[j] = t
			parent[j] = m
			visited[j] = 1
print(ans)
print(len(power_set))
for i in power_set:
	print(i + 1, end=' ')
print()
print(len(connect))
for i in connect:
	print(i[0] + 1, i[1] + 1)


n = int(input())
cord = [[*map(int, input().split())] for _ in range(n)]
c = [*map(int, input().split())]
k = [*map(int, input().split())]
plant = set()
covered = set()
parent = [-1] * n
sum = 0
for _ in range(n):
	(cost, idx) = min(([cost, idx] for (idx, cost) in enumerate(c) if idx not in covered))
	sum += cost
	covered.add(idx)
	if parent[idx] == -1:
		plant.add(idx)
	for i in range(n):
		if i in covered:
			continue
		c_l = (k[i] + k[idx]) * (abs(cord[i][0] - cord[idx][0]) + abs(cord[i][1] - cord[idx][1]))
		if c_l < c[i]:
			c[i] = c_l
			parent[i] = idx
print('{}\n{}'.format(sum, len(plant)))
print(*map(lambda x: x + 1, plant))
links = 0
out = ''
for (i, _) in enumerate(parent):
	if _ != -1:
		links += 1
		out += '\n' + str(_ + 1) + ' ' + str(i + 1)
print(links, out)


import sys
input = sys.stdin.readline
n = int(input())
X = [[0] * 7 for _ in range(n)]
for i in range(n):
	(x, y) = map(int, input().split())
	(X[i][0], X[i][1], X[i][2]) = (i + 1, x, y)
C = [int(i) for i in input().split()]
K = [int(i) for i in input().split()]
for i in range(n):
	(X[i][3], X[i][4]) = (C[i], K[i])
ans_am = 0
ans_ps = 0
Ans = []
ans_con = 0
Con = []

def m(X):
	ret = 0
	cur = X[0][3]
	for i in range(1, len(X)):
		if X[i][3] < cur:
			ret = i
			cur = X[i][3]
	return ret

def cost(k, ki, x, xi, y, yi):
	return (k + ki) * (abs(x - xi) + abs(y - yi))
while X:
	r = m(X)
	(ind, x, y, c, k, flag, source) = X.pop(r)
	ans_am += c
	if not flag:
		ans_ps += 1
		Ans.append(ind)
	else:
		ans_con += 1
		Con.append((ind, source))
	for i in range(len(X)):
		(indi, xi, yi, ci, ki, flagi, sourcei) = X[i]
		co = cost(k, ki, x, xi, y, yi)
		if co < ci:
			(X[i][3], X[i][5], X[i][6]) = (co, 1, ind)
print(ans_am)
print(ans_ps)
print(*Ans)
print(ans_con)
for (i, j) in Con:
	print(i, j)


import sys
reader = (list(map(int, s.split())) for s in sys.stdin)
(n,) = next(reader)
cities = [None]
for _ in range(n):
	(x, y) = next(reader)
	cities.append((x, y))
cs = [None] + list(next(reader))
ks = [None] + list(next(reader))
n += 1
g = [[None] * n for _ in range(n)]
for i in range(1, n):
	for j in range(i + 1, n):
		wire = ks[i] + ks[j]
		dist = abs(cities[i][0] - cities[j][0]) + abs(cities[i][1] - cities[j][1])
		g[i][j] = g[j][i] = wire * dist
for i in range(1, n):
	g[0][i] = g[i][0] = cs[i]
for i in range(n):
	g[i][i] = float('inf')
totalCost = 0
stations = []
connections = []
connCosts = {i: float('inf') for i in range(n)}
connTo = [-1] * n
start = 0
connCosts[start] = 0
while connCosts:
	v = min(connCosts, key=connCosts.get)
	if connCosts[v] == float('inf'):
		break
	fromNode = connTo[v]
	if not fromNode:
		totalCost += g[v][fromNode]
		stations.append(v)
	elif fromNode > 0:
		totalCost += g[v][fromNode]
		connections.append((v, fromNode))
	connCosts.pop(v)
	for (to, cost) in list(connCosts.items()):
		if g[v][to] < connCosts[to]:
			connCosts[to] = g[v][to]
			connTo[to] = v
myprint = sys.stdout.write
myprint(str(totalCost) + '\n')
myprint(str(len(stations)) + '\n')
[myprint(str(st) + ' ') for st in stations]
myprint(str(len(connections)) + '\n')
[myprint(str(c1) + ' ' + str(c2) + '\n') for (c1, c2) in connections]


n = int(input())
X = [[0] * 7 for _ in range(n)]
for i in range(n):
	(x, y) = map(int, input().split())
	X[i][0] = i + 1
	X[i][1] = x
	X[i][2] = y
C = [int(i) for i in input().split()]
K = [int(i) for i in input().split()]
for i in range(n):
	X[i][3] = C[i]
	X[i][4] = K[i]
X.sort(key=lambda x: x[3])
ans_am = 0
ans_ps = 0
Ans = []
ans_con = 0
Con = []
while X:
	(ind, x, y, c, k, flag, source) = X.pop(0)
	ans_am += c
	if flag == 0:
		ans_ps += 1
		Ans.append(ind)
	else:
		ans_con += 1
		Con.append([ind, source])
	for i in range(len(X)):
		(indi, xi, yi, ci, ki, flagi, sourcei) = X[i]
		if (k + ki) * (abs(x - xi) + abs(y - yi)) < ci:
			X[i][3] = (k + ki) * (abs(x - xi) + abs(y - yi))
			X[i][5] = 1
			X[i][6] = ind
	X.sort(key=lambda x: x[3])
print(ans_am)
print(ans_ps)
print(*Ans)
print(ans_con)
for (i, j) in Con:
	print(i, j)


import math
n = int(input())
cityNo = [0] * n
for i in range(n):
	cityNo[i] = list(map(int, input().split()))
cost = list(map(int, input().split()))
ks = list(map(int, input().split()))
powerStation = [0] * n
totalCost = 0
req_Powerstation = []
notReq_Powerstation = []
totalCost = 0
established = {}
updated = [-1] * n
for j in range(n):
	city = -1
	mini = 9999999999999999
	for i in range(n):
		if mini > cost[i] and i not in established:
			city = i
			mini = cost[i]
	if updated[city] == -1:
		req_Powerstation.append(city + 1)
	else:
		notReq_Powerstation.append([city + 1, updated[city] + 1])
	totalCost += cost[city]
	established[city] = 1
	for i in range(n):
		cost_From_City = (ks[i] + ks[city]) * (abs(cityNo[i][0] - cityNo[city][0]) + abs(cityNo[i][1] - cityNo[city][1]))
		if cost_From_City < cost[i]:
			cost[i] = cost_From_City
			updated[i] = city
print(totalCost)
print(len(req_Powerstation))
print(*req_Powerstation)
print(len(notReq_Powerstation))
for i in range(len(notReq_Powerstation)):
	print(*notReq_Powerstation[i])