D. Shichikuji and Power Grid

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

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](images/cf_1245_D/1.png)
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.

solutions: ["def main():\n\tn = int(input())\n\txy = []\n\tfor _ in range(n):\n\t\txy.append(readIntArr())\n\tc = readIntArr()\n\tk = readIntArr()\n\n\tdef getCost(i, j):\n\t\tif i == n:\n\t\t\treturn c[j]\n\t\tif j == n:\n\t\t\treturn c[i]\n\t\t(xi, yi) = xy[i]\n\t\t(xj, yj) = xy[j]\n\t\treturn (k[i] + k[j]) * (abs(xi - xj) + abs(yi - yj))\n\ttotal = 0\n\tpoweredCities = []\n\tconnectedCities = []\n\tvisited = [False] * (n + 1)\n\tcostCheapest = [inf] * (n + 1)\n\tfromCheapest = [-1] * (n + 1)\n\tcurrCity = 0\n\tvisited[currCity] = True\n\tfor _ in range(n):\n\t\tfor destination in range(n + 1):\n\t\t\tif currCity == destination:\n\t\t\t\tcontinue\n\t\t\tif visited[destination]:\n\t\t\t\tcontinue\n\t\t\tif getCost(currCity, destination) < costCheapest[destination]:\n\t\t\t\tcostCheapest[destination] = getCost(currCity, destination)\n\t\t\t\tfromCheapest[destination] = currCity\n\t\tminCost = inf\n\t\tminCityFrom = -1\n\t\tminCityTo = -1\n\t\tfor destination in range(n + 1):\n\t\t\tif currCity == destination:\n\t\t\t\tcontinue\n\t\t\tif visited[destination]:\n\t\t\t\tcontinue\n\t\t\tif costCheapest[destination] < minCost:\n\t\t\t\tminCost = costCheapest[destination]\n\t\t\t\tminCityFrom = fromCheapest[destination]\n\t\t\t\tminCityTo = destination\n\t\tassert minCityFrom != -1\n\t\ttotal += minCost\n\t\tvisited[minCityTo] = True\n\t\tif minCityFrom == n:\n\t\t\tpoweredCities.append(minCityTo + 1)\n\t\telif minCityTo == n:\n\t\t\tpoweredCities.append(minCityFrom + 1)\n\t\telse:\n\t\t\tconnectedCities.append([minCityFrom + 1, minCityTo + 1])\n\t\tcurrCity = minCityTo\n\tprint(total)\n\tprint(len(poweredCities))\n\toneLineArrayPrint(poweredCities)\n\tprint(len(connectedCities))\n\tmultiLineArrayOfArraysPrint(connectedCities)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultVal, dimensionArr):\n\tdv = defaultVal\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(x, y):\n\tprint('? {} {}'.format(x, y))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nMOD = 10 ** 9 + 7\nfor _abc in range(1):\n\tmain()\n", "import sys\nreader = (map(int, s.split()) for s in sys.stdin)\n(n,) = next(reader)\nlocs = [tuple(next(reader)) for _ in range(n)]\ncs = list(next(reader))\nks = list(next(reader))\ntotalCost = 0\nstations = []\nconnections = []\nconnCosts = {i: cost for (i, cost) in enumerate(cs)}\nconnTo = [-1] * n\nwhile connCosts:\n\tv = min(connCosts, key=connCosts.get)\n\ttotalCost += connCosts[v]\n\tif connCosts[v] < cs[v]:\n\t\tto = connTo[v]\n\t\tconnections.append((v, to))\n\telse:\n\t\tstations.append(v)\n\tconnCosts.pop(v)\n\tfor (to, cost) in connCosts.items():\n\t\twire = ks[v] + ks[to]\n\t\tdist = abs(locs[v][0] - locs[to][0]) + abs(locs[v][1] - locs[to][1])\n\t\tnewCost = wire * dist\n\t\tif connCosts[to] > newCost:\n\t\t\tconnCosts[to] = newCost\n\t\t\tconnTo[to] = v\nmyprint = sys.stdout.write\nmyprint(str(totalCost) + '\\n')\nmyprint(str(len(stations)) + '\\n')\n[myprint(str(st + 1) + ' ') for st in stations]\nmyprint(str(len(connections)) + '\\n')\n[myprint(str(c1 + 1) + ' ' + str(c2 + 1) + '\\n') for (c1, c2) in connections]\n", "import os, sys\nfrom io import BytesIO, IOBase\n\ndef prims(n, path, st, z, c, conn):\n\t(ans, where, visi) = (0, [z] * n, [0] * n)\n\tnode = [path[j][z] for j in range(n)]\n\tvisi[z] = 1\n\twhile 1:\n\t\t(le, y, dig) = (float('inf'), -1, 0)\n\t\tfor j in range(n):\n\t\t\tif visi[j]:\n\t\t\t\tcontinue\n\t\t\tif node[j] < c[j] and node[j] < le:\n\t\t\t\t(le, y, dig) = (node[j], j, 0)\n\t\t\telif c[j] < node[j] and c[j] < le:\n\t\t\t\t(le, y, dig) = (c[j], j, 1)\n\t\tif le == float('inf'):\n\t\t\treturn ans\n\t\tvisi[y] = 1\n\t\tif not dig:\n\t\t\tconn.append((where[y] + 1, y + 1))\n\t\telse:\n\t\t\tst.append(y + 1)\n\t\tans += le\n\t\tfor (j, i) in enumerate(path[y]):\n\t\t\tif not visi[j] and i < node[j]:\n\t\t\t\t(node[j], where[j]) = (i, y)\n\ndef main():\n\tn = int(input())\n\t(x, y) = ([], [])\n\tfor (a1, b1) in iter([map(int, input().split()) for _ in range(n)]):\n\t\tx.append(a1)\n\t\ty.append(b1)\n\tc = list(map(float, input().split()))\n\tk = list(map(float, input().split()))\n\tpath = [[0] * n for _ in range(n)]\n\tfor i in range(n):\n\t\tfor j in range(i + 1, n):\n\t\t\tz = (k[i] + k[j]) * (abs(x[i] - x[j]) + abs(y[i] - y[j]))\n\t\t\t(path[i][j], path[j][i]) = (z, z)\n\t(z, ans, st, conn) = (c.index(min(c)), min(c), [], [])\n\tst.append(z + 1)\n\tans += prims(n, path, st, z, c, conn)\n\tprint(int(ans))\n\tprint(len(st))\n\tprint(*st)\n\tprint(len(conn))\n\tfor i in conn:\n\t\tprint(*i)\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "from collections import deque\nfrom math import inf\n\ndef run_testcase():\n\tn = int(input())\n\tcoords = [None] * (n + 1)\n\tfor i in range(1, n + 1):\n\t\tcoords[i] = [int(x) for x in input().split()]\n\tci = [0] + [int(x) for x in input().split()]\n\tki = [0] + [int(x) for x in input().split()]\n\n\tdef cost(i, j):\n\t\tif i == j:\n\t\t\treturn 0\n\t\tif i > j:\n\t\t\t(i, j) = (j, i)\n\t\tif i == 0:\n\t\t\treturn ci[j]\n\t\treturn (abs(coords[i][0] - coords[j][0]) + abs(coords[i][1] - coords[j][1])) * (ki[i] + ki[j])\n\tcurrent_cost = 0\n\ttree = set([0])\n\trest = set(range(1, n + 1))\n\tincluded = [True] + [False] * n\n\tconnections = deque()\n\tconnections_to_station = 0\n\tmin_attach_cost = [(0, 0)] + [(cost(0, j), 0) for j in range(1, n + 1)]\n\twhile len(tree) < n + 1:\n\t\tmin_pair = (0, 0)\n\t\tmin_cost = inf\n\t\tfor node in rest:\n\t\t\tif min_attach_cost[node][0] < min_cost:\n\t\t\t\tmin_pair = (min_attach_cost[node][1], node)\n\t\t\t\tmin_cost = min_attach_cost[node][0]\n\t\ttree.add(min_pair[1])\n\t\tincluded[min_pair[1]] = True\n\t\tcurrent_cost += min_cost\n\t\trest.remove(min_pair[1])\n\t\tfor node in rest:\n\t\t\tif cost(min_pair[1], node) < min_attach_cost[node][0]:\n\t\t\t\tmin_attach_cost[node] = (cost(min_pair[1], node), min_pair[1])\n\t\tmin_pair = tuple(sorted(min_pair))\n\t\tif min_pair[0] == 0:\n\t\t\tconnections.appendleft(min_pair)\n\t\t\tconnections_to_station += 1\n\t\telse:\n\t\t\tconnections.append(min_pair)\n\tconnections_list = list(connections)\n\tprint(current_cost)\n\tprint(connections_to_station)\n\tprint(' '.join(map(lambda x: str(x[1]), connections_list[:connections_to_station])))\n\tprint(len(connections_list) - connections_to_station)\n\tfor i in range(connections_to_station, len(connections_list)):\n\t\tprint(connections_list[i][0], connections_list[i][1])\nrun_testcase()\n", "import math\nn = int(input())\ncoor = []\n\ndef dis(x, y):\n\treturn abs(x[0] - y[0]) + abs(y[1] - x[1])\nfor i in range(n):\n\t(u, v) = map(int, input().split())\n\tcoor.append((u, v))\ncost = list(map(int, input().split()))\nk = list(map(int, input().split()))\nd = {}\npower_st = []\nvis = [0] * n\nconnect = []\nparent = [-1 for i in range(n)]\nfor i in range(n):\n\td[i] = cost[i]\nans = 0\nfor i in range(n):\n\tm = min(d, key=d.get)\n\tif vis[m] == 0:\n\t\tpower_st.append(m)\n\telse:\n\t\tconnect.append([m, parent[m]])\n\tans = ans + d[m]\n\tdel d[m]\n\tfor j in d.keys():\n\t\tt = dis(coor[m], coor[j]) * (k[m] + k[j])\n\t\tif t < d[j]:\n\t\t\td[j] = t\n\t\t\tparent[j] = m\n\t\t\tvis[j] = 1\nprint(ans)\nprint(len(power_st))\nfor i in power_st:\n\tprint(i + 1, end=' ')\nprint()\nprint(len(connect))\nfor i in connect:\n\tprint(i[0] + 1, i[1] + 1)\n", "def prim(n, adj):\n\ttotal_weight = 0\n\t(selected, min_e) = ([False] * n, [[float('inf'), -1] for _ in range(n)])\n\tmst_edges = []\n\tmin_e[0][0] = 0\n\tfor i in range(n):\n\t\tv = -1\n\t\tfor j in range(n):\n\t\t\tif not selected[j] and (v == -1 or min_e[j][0] < min_e[v][0]):\n\t\t\t\tv = j\n\t\tif min_e[v][0] == float('inf'):\n\t\t\treturn (None, None)\n\t\tselected[v] = True\n\t\ttotal_weight += min_e[v][0]\n\t\tif min_e[v][1] != -1:\n\t\t\tmst_edges.append((v, min_e[v][1]))\n\t\tfor to in range(n):\n\t\t\tif adj[v][to] < min_e[to][0]:\n\t\t\t\tmin_e[to] = [adj[v][to], v]\n\treturn (mst_edges, total_weight)\n\ndef main():\n\tn = int(input())\n\txes = []\n\tyes = []\n\tfor _ in range(n):\n\t\t(x, y) = readIntArr()\n\t\txes.append(x)\n\t\tyes.append(y)\n\tc = readIntArr()\n\tk = readIntArr()\n\n\tdef getCost(i, j):\n\t\tif i == n:\n\t\t\treturn c[j]\n\t\tif j == n:\n\t\t\treturn c[i]\n\t\treturn (k[i] + k[j]) * (abs(xes[i] - xes[j]) + abs(yes[i] - yes[j]))\n\tadj = []\n\tfor i in range(n + 1):\n\t\tarr = []\n\t\tfor j in range(n + 1):\n\t\t\tif i == j:\n\t\t\t\tarr.append(inf)\n\t\t\telse:\n\t\t\t\tarr.append(getCost(i, j))\n\t\tadj.append(arr)\n\t(edges, totalCost) = prim(n + 1, adj)\n\tcityLinks = []\n\tpowerStations = []\n\tfor (i, j) in edges:\n\t\tif i == n:\n\t\t\tpowerStations.append(j + 1)\n\t\telif j == n:\n\t\t\tpowerStations.append(i + 1)\n\t\telse:\n\t\t\tcityLinks.append([i + 1, j + 1])\n\tprint(totalCost)\n\tprint(len(powerStations))\n\toneLineArrayPrint(powerStations)\n\tprint(len(cityLinks))\n\tmultiLineArrayOfArraysPrint(cityLinks)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultVal, dimensionArr):\n\tdv = defaultVal\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(x, y):\n\tprint('? {} {}'.format(x, y))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nMOD = 10 ** 9 + 7\nfor _abc in range(1):\n\tmain()\n", "import bisect\nimport functools\nimport math\nimport sys\nfrom collections import defaultdict\nrt = lambda : map(int, input().split())\nri = lambda : int(input())\nrl = lambda : list(map(int, input().split()))\n\ndef dist(x1, y1, x2, y2):\n\treturn abs(x1 - x2) + abs(y1 - y2)\n\ndef main():\n\tn = ri()\n\t(x, y) = ([0] * n, [0] * n)\n\tfor i in range(n):\n\t\t(x[i], y[i]) = rt()\n\tc = rl()\n\tk = rl()\n\tval = c.copy()\n\tused = [False] * n\n\tlink = [-1] * n\n\tto_build = []\n\tfor _ in range(n):\n\t\tmin_index = -1\n\t\tmin_val = math.inf\n\t\tfor i in range(n):\n\t\t\tif not used[i] and val[i] < min_val:\n\t\t\t\tmin_index = i\n\t\t\t\tmin_val = val[i]\n\t\tused[min_index] = True\n\t\tif link[min_index] == -1:\n\t\t\tto_build.append(min_index + 1)\n\t\tfor i in range(n):\n\t\t\tif not used[i]:\n\t\t\t\tto_link = (k[i] + k[min_index]) * dist(x[i], y[i], x[min_index], y[min_index])\n\t\t\t\tif to_link < val[i]:\n\t\t\t\t\tval[i] = to_link\n\t\t\t\t\tlink[i] = min_index\n\tprint(sum(val))\n\tprint(len(to_build))\n\tprint(*to_build)\n\tprint(len([x for x in link if x > -1]))\n\tfor i in range(n):\n\t\tif link[i] > -1:\n\t\t\tprint(i + 1, link[i] + 1)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "N = int(input())\nXY = [list(map(int, input().split())) for _ in range(N)]\nC = list(map(int, input().split()))\nK = list(map(int, input().split()))\nCC = [-1] * N\nAns = [-2] * N\ntotal_cost = 0\nfor _ in range(N):\n\tmi = float('inf')\n\tfor (i, (c, an)) in enumerate(zip(C, Ans)):\n\t\tif an == -2 and mi > c:\n\t\t\tmi = c\n\t\t\tami = i\n\ttotal_cost += mi\n\tAns[ami] = CC[ami]\n\tk1 = K[ami]\n\t(x1, y1) = XY[ami]\n\tfor (i, (k2, (x2, y2))) in enumerate(zip(K, XY)):\n\t\tnew_cost = (k1 + k2) * (abs(x1 - x2) + abs(y1 - y2))\n\t\tif C[i] > new_cost:\n\t\t\tC[i] = new_cost\n\t\t\tCC[i] = ami\nprint(total_cost)\ncnt = Ans.count(-1)\nprint(cnt)\nA = []\nB = []\nfor (i, a) in enumerate(Ans, 1):\n\tif a == -1:\n\t\tA.append(i)\n\telse:\n\t\tB.append((i, a + 1))\nprint(' '.join(map(str, A)))\nprint(N - cnt)\nfor (a, b) in B:\n\tprint(a, b)\n", "from __future__ import division, print_function\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\nfrom itertools import *\nimport bisect\nfrom heapq import *\nfrom math import *\nfrom copy import *\nfrom collections import deque\nfrom collections import Counter as counter\nfrom itertools import combinations as comb\nfrom itertools import permutations as permutate\nfrom bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom bisect import bisect\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\nfrom types import GeneratorType\n\ndef iterative(f, stack=[]):\n\n\tdef wrapped_func(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\tto = f(*args, **kwargs)\n\t\twhile True:\n\t\t\tif type(to) is GeneratorType:\n\t\t\t\tstack.append(to)\n\t\t\t\tto = next(to)\n\t\t\t\tcontinue\n\t\t\tstack.pop()\n\t\t\tif not stack:\n\t\t\t\tbreak\n\t\t\tto = stack[-1].send(to)\n\t\treturn to\n\treturn wrapped_func\nmod = 1000000007\n\ndef inp():\n\treturn sys.stdin.readline().rstrip('\\r\\n')\n\ndef out(var):\n\tsys.stdout.write(str(var))\n\ndef lis():\n\treturn list(map(int, inp().split()))\n\ndef stringlis():\n\treturn list(map(str, inp().split()))\n\ndef sep():\n\treturn map(int, inp().split())\n\ndef strsep():\n\treturn map(str, inp().split())\n\ndef zerolist(n):\n\treturn [0] * n\n\ndef nextline():\n\tout('\\n')\n\ndef testcase(t):\n\tfor pp in range(t):\n\t\tsolve(pp)\n\ndef printlist(a):\n\tfor p in range(0, len(a)):\n\t\tout(str(a[p]) + ' ')\n\ndef google(p):\n\tprint('Case #' + str(p) + ': ', end='')\n\ndef lcm(a, b):\n\treturn a * b // gcd(a, b)\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n\ndef ncr(n, r):\n\treturn factorial(n) // (factorial(r) * factorial(max(n - r, 1)))\n\ndef isPrime(n):\n\tif n <= 1:\n\t\treturn False\n\tif n <= 3:\n\t\treturn True\n\tif n % 2 == 0 or n % 3 == 0:\n\t\treturn False\n\ti = 5\n\twhile i * i <= n:\n\t\tif n % i == 0 or n % (i + 2) == 0:\n\t\t\treturn False\n\t\ti = i + 6\n\treturn True\n\ndef distgrid(a, b, k):\n\treturn k * (abs(a[0] - b[0]) + abs(a[1] - b[1]))\n\ndef solve(case):\n\tn = int(inp())\n\tcoor = []\n\tfor i in range(n):\n\t\t(x, y) = sep()\n\t\tcoor.append((x, y))\n\tc = lis()\n\tk = lis()\n\tvis = [False] * n\n\twired = [-1] * n\n\tpower = []\n\tconnectn = []\n\tans = 0\n\tfor i in range(n):\n\t\tmini = 10 ** 10\n\t\tfor j in range(n):\n\t\t\tif vis[j]:\n\t\t\t\tcontinue\n\t\t\tif c[j] < mini:\n\t\t\t\tmini = c[j]\n\t\t\t\tcity = j\n\t\tans += mini\n\t\tif wired[city] != -1:\n\t\t\tconnectn.append((city, wired[city]))\n\t\telse:\n\t\t\tpower.append(city)\n\t\tvis[city] = True\n\t\tfor j in range(n):\n\t\t\tnew = distgrid(coor[city], coor[j], k[city] + k[j])\n\t\t\tif new < c[j]:\n\t\t\t\tc[j] = new\n\t\t\t\twired[j] = city\n\tprint(ans)\n\tprint(len(power))\n\tprint(' '.join((str(power[i] + 1) for i in range(len(power)))))\n\tprint(len(connectn))\n\tfor i in range(len(connectn)):\n\t\tprint(connectn[i][0] + 1, connectn[i][1] + 1)\ntestcase(1)\n", "n = int(input())\npos = [[*map(int, input().split())] for i in range(n)]\n(*c,) = map(int, input().split())\n(*k,) = map(int, input().split())\nused = [False for i in range(n)]\nparent = [-1 for i in range(n)]\nplants = []\nconnections = []\nans = 0\n_n = n\nwhile _n:\n\t_n -= 1\n\t(mn, u) = min([(ci, i) for (i, ci) in enumerate(c) if not used[i]])\n\tans += mn\n\tused[u] = True\n\tif parent[u] == -1:\n\t\tplants.append(u)\n\telse:\n\t\tconnections.append((min(parent[u], u), max(parent[u], u)))\n\tfor i in range(n):\n\t\tcon_cost = (k[u] + k[i]) * (abs(pos[u][0] - pos[i][0]) + abs(pos[u][1] - pos[i][1]))\n\t\tif con_cost < c[i]:\n\t\t\tc[i] = con_cost\n\t\t\tparent[i] = u\nprint(ans)\nprint(len(plants))\nfor p in sorted(plants):\n\tprint(p + 1, end=' ')\nprint('')\nprint(len(connections))\nfor con in connections:\n\tprint(con[0] + 1, con[1] + 1)\n", "from math import *\nc = int(input())\nx = [0] * c\ny = [0] * c\nvu = [False] * c\nfor i in range(c):\n\t(x[i], y[i]) = [int(s) for s in input().split()]\nprix = [int(s) for s in input().split()]\nfil = [int(s) for s in input().split()]\nanc = [-1] * c\npmin = prix.copy()\nv = 0\npl = []\ne = 0\nppl = []\ntot = 0\nfor i in range(c):\n\tpmina = 100000000000000000000000\n\tfor j in range(c):\n\t\tif not vu[j] and pmin[j] < pmina:\n\t\t\tpmini = j\n\t\t\tpmina = pmin[j]\n\tvu[pmini] = True\n\ttot += pmina\n\tif anc[pmini] == -1:\n\t\tv += 1\n\t\tpl.append(str(pmini + 1))\n\telse:\n\t\te += 1\n\t\tppl.append([str(pmini + 1), str(anc[pmini] + 1)])\n\tfor j in range(c):\n\t\tif (abs(x[pmini] - x[j]) + abs(y[pmini] - y[j])) * (fil[pmini] + fil[j]) < pmin[j]:\n\t\t\tpmin[j] = (abs(x[pmini] - x[j]) + abs(y[pmini] - y[j])) * (fil[pmini] + fil[j])\n\t\t\tanc[j] = pmini\nprint(tot)\nprint(v)\nprint(' '.join(pl))\nprint(e)\nfor i in ppl:\n\tprint(' '.join(i))\n", "from sys import stdin, stdout\nfrom collections import Counter\n\ndef ai():\n\treturn list(map(int, stdin.readline().split()))\n\ndef ei():\n\treturn map(int, stdin.readline().split())\n\ndef ip():\n\treturn int(stdin.readline().strip())\n\ndef op(ans):\n\treturn stdout.write(str(ans) + '\\n')\nn = ip()\npos = [ai() for i in range(n)]\nc = ai()\nk = ai()\nconnections = []\nplants = []\nused = [False] * n\nparent = [-1] * n\nans = 0\nn_ = n\nwhile n_:\n\tn_ -= 1\n\t(mn, u) = min([(ci, i) for (i, ci) in enumerate(c) if not used[i]])\n\tans += mn\n\tused[u] = True\n\tif parent[u] == -1:\n\t\tplants.append(u)\n\telse:\n\t\tconnections.append((min(parent[u], u), max(parent[u], u)))\n\tfor i in range(n):\n\t\tcon_cost = (k[u] + k[i]) * (abs(pos[u][0] - pos[i][0]) + abs(pos[u][1] - pos[i][1]))\n\t\tif con_cost < c[i]:\n\t\t\tc[i] = con_cost\n\t\t\tparent[i] = u\nprint(ans)\nprint(len(plants))\nfor i in sorted(plants):\n\tprint(i + 1, end=' ')\nprint()\nprint(len(connections))\nfor i in connections:\n\tprint(i[0] + 1, i[1] + 1)\n", "import sys\nreader = (map(int, s.split()) for s in sys.stdin)\n(n,) = next(reader)\ncities = [None]\nfor _ in range(n):\n\t(x, y) = next(reader)\n\tcities.append((x, y))\ncs = [None] + list(next(reader))\nks = [None] + list(next(reader))\nn += 1\ng = [[None] * n for _ in range(n)]\nfor i in range(1, n):\n\tfor j in range(i + 1, n):\n\t\twire = ks[i] + ks[j]\n\t\tdist = abs(cities[i][0] - cities[j][0]) + abs(cities[i][1] - cities[j][1])\n\t\tg[i][j] = g[j][i] = wire * dist\nfor i in range(1, n):\n\tg[0][i] = g[i][0] = cs[i]\nfor i in range(n):\n\tg[i][i] = float('inf')\ntotalCost = 0\nstations = []\nconnections = []\nused = [False] * n\nmin_e = [float('inf')] * n\nsel_e = [-1] * n\nstart = 0\nmin_e[start] = 0\nfor i in range(n):\n\tv = -1\n\tfor j in range(n):\n\t\tif not used[j] and (v == -1 or min_e[j] < min_e[v]):\n\t\t\tv = j\n\tused[v] = True\n\tfromNode = sel_e[v]\n\tif not fromNode:\n\t\ttotalCost += g[v][fromNode]\n\t\tstations.append(v)\n\telif fromNode > 0:\n\t\ttotalCost += g[v][fromNode]\n\t\tconnections.append((v, fromNode))\n\tfor to in range(n):\n\t\tif g[v][to] < min_e[to]:\n\t\t\tmin_e[to] = g[v][to]\n\t\t\tsel_e[to] = v\nmyprint = sys.stdout.write\nmyprint(str(totalCost) + '\\n')\nmyprint(str(len(stations)) + '\\n')\n[myprint(str(st) + ' ') for st in stations]\nmyprint(str(len(connections)) + '\\n')\n[myprint(str(c1) + ' ' + str(c2) + '\\n') for (c1, c2) in connections]\n", "import sys\ninput = sys.stdin.readline\nn = int(input())\nT = [tuple(map(int, input().split())) for i in range(n)]\nC = list(map(int, input().split()))\nK = list(map(int, input().split()))\nimport heapq\nH = []\nfor (i, c) in enumerate(C):\n\tH.append((c, i + 1))\nheapq.heapify(H)\nANS = 0\nUSE = [0] * (n + 1)\nANS1 = []\nANS2 = []\nwhile H:\n\tx = heapq.heappop(H)\n\tif len(x) == 2:\n\t\t(cost, town) = x\n\t\tif USE[town] == 1:\n\t\t\tcontinue\n\t\tANS += cost\n\t\tUSE[town] = 1\n\t\tANS1.append(town)\n\t\t(xt, yt) = T[town - 1]\n\t\tfor i in range(n):\n\t\t\tif USE[i + 1] == 1:\n\t\t\t\tcontinue\n\t\t\tcostp = (abs(T[i][0] - xt) + abs(T[i][1] - yt)) * (K[i] + K[town - 1])\n\t\t\tif costp < C[i]:\n\t\t\t\tC[i] = costp\n\t\t\t\theapq.heappush(H, (costp, town, i + 1))\n\telse:\n\t\t(cost, town1, town2) = x\n\t\tif USE[town1] == 1 and USE[town2] == 1:\n\t\t\tcontinue\n\t\tANS += cost\n\t\tUSE[town2] = 1\n\t\tANS2.append((town1, town2))\n\t\t(xt, yt) = T[town2 - 1]\n\t\tfor i in range(n):\n\t\t\tif USE[i + 1] == 1:\n\t\t\t\tcontinue\n\t\t\tcostp = (abs(T[i][0] - xt) + abs(T[i][1] - yt)) * (K[i] + K[town2 - 1])\n\t\t\tif costp < C[i]:\n\t\t\t\tC[i] = costp\n\t\t\t\theapq.heappush(H, (costp, town2, i + 1))\nsys.stdout.write(str(ANS) + '\\n')\nsys.stdout.write(str(len(ANS1)) + '\\n')\nprint(*ANS1)\nsys.stdout.write(str(len(ANS2)) + '\\n')\nfor (x, y) in ANS2:\n\tsys.stdout.write(str(x) + ' ' + str(y) + '\\n')\n", "import sys\nreader = (list(map(int, s.split())) for s in sys.stdin)\n(n,) = next(reader)\nxy = []\nfor _ in range(n):\n\t(x, y) = next(reader)\n\txy.append([x, y])\nc = list(next(reader))\nk = list(next(reader))\ngraph = [[0 for _ in range(n + 1)] for _i in range(n + 1)]\nfor i in range(n):\n\tfor j in range(i + 1, n):\n\t\tcost = (abs(xy[i][0] - xy[j][0]) + abs(xy[i][1] - xy[j][1])) * (k[i] + k[j])\n\t\tgraph[i][j] = graph[j][i] = cost\n\tgraph[n][i] = graph[i][n] = c[i]\n\ndef primMST():\n\tkey = [1000000000000] * (n + 1)\n\tparent = [None] * (n + 1)\n\tkey[0] = 0\n\tmstSet = [False] * (n + 1)\n\tparent[0] = -1\n\tfor cout in range(n + 1):\n\t\tmn = 1000000000000\n\t\tfor v in range(n + 1):\n\t\t\tif key[v] < mn and mstSet[v] == False:\n\t\t\t\tmn = key[v]\n\t\t\t\tmin_index = v\n\t\tu = min_index\n\t\tmstSet[u] = True\n\t\tfor v in range(n + 1):\n\t\t\tif graph[u][v] > 0 and mstSet[v] == False and (key[v] > graph[u][v]):\n\t\t\t\tkey[v] = graph[u][v]\n\t\t\t\tparent[v] = u\n\tvss = 0\n\tcost = 0\n\tfor i in range(1, n + 1):\n\t\tif parent[i] == n or i == n:\n\t\t\tvss += 1\n\t\tcost += graph[i][parent[i]]\n\tmyprint = sys.stdout.write\n\tmyprint(str(cost) + '\\n')\n\tmyprint(str(vss) + '\\n')\n\tvs = [0] * vss\n\tes = [[]] * (n - vss)\n\t(k1, k2) = (0, 0)\n\tfor i in range(1, n + 1):\n\t\tif parent[i] == n:\n\t\t\tvs[k1] = i + 1\n\t\t\tk1 += 1\n\t\telif i == n:\n\t\t\tvs[k1] = parent[i] + 1\n\t\t\tk1 += 1\n\t\telse:\n\t\t\tes[k2] = [i + 1, parent[i] + 1]\n\t\t\tk2 += 1\n\t[myprint(str(st) + ' ') for st in vs]\n\tmyprint('\\n')\n\tmyprint(str(len(es)) + '\\n')\n\t[myprint(str(i[0]) + ' ' + str(i[1]) + '\\n') for i in es]\nprimMST()\n", "import sys\nreadline = sys.stdin.readline\nrdw = lambda : readline().rstrip()\nrdws = lambda : readline().split()\nrdwl = lambda : list(readline().split())\nrdi = lambda : int(readline())\nrdis = lambda : list(map(int, readline().split()))\nrdil = lambda : list(map(int, readline().split()))\nrdilrows = lambda cnt: [rdil() for _ in range(cnt)]\n\ndef solve():\n\tres = 0\n\tbld = []\n\twire = []\n\tn = rdi()\n\tcities = rdilrows(n)\n\tc = rdil()\n\tp = [-1 for i in range(n)]\n\tk = rdil()\n\tused = set()\n\tused.add(-1)\n\tfor i in range(n):\n\t\t(cost, bst) = min([(c[i], i) for i in range(n) if i not in used])\n\t\tpar = p[bst]\n\t\tused.add(bst)\n\t\tres += cost\n\t\tif par == -1:\n\t\t\tbld.append(bst + 1)\n\t\telse:\n\t\t\twire.append((bst + 1, par + 1))\n\t\tfor j in range(n):\n\t\t\tif j not in used:\n\t\t\t\twcost = (k[bst] + k[j]) * (abs(cities[bst][0] - cities[j][0]) + abs(cities[bst][1] - cities[j][1]))\n\t\t\t\tif wcost < c[j]:\n\t\t\t\t\tc[j] = wcost\n\t\t\t\t\tp[j] = bst\n\tsys.stdout.write(f'{res}\\n')\n\tsys.stdout.write(f'{len(bld)}\\n')\n\tsys.stdout.write(f\"{' '.join(map(str, bld))}\\n\")\n\tsys.stdout.write(f'{len(wire)}\\n')\n\tfor i in range(len(wire)):\n\t\tsys.stdout.write(f'{wire[i][0]} {wire[i][1]}\\n')\ntests = 1\nfor testnum in range(tests):\n\tsolve()\n", "def prim(matrix, inf=10 ** 18):\n\tn = len(matrix)\n\tcosts = [inf] + [inf - 1] * (n - 1)\n\tnearest = [-1] * n\n\tcurrent = 0\n\ttotal_cost = 0\n\t(build, connect) = ([], [])\n\tfor _ in range(n - 1):\n\t\tmin_cost = inf\n\t\t(src, dest) = (-1, -1)\n\t\tfor i in range(n):\n\t\t\tif costs[i] == inf:\n\t\t\t\tcontinue\n\t\t\tif matrix[current][i] < costs[i]:\n\t\t\t\tcosts[i] = matrix[current][i]\n\t\t\t\tnearest[i] = current\n\t\t\tif min_cost > costs[i]:\n\t\t\t\tmin_cost = costs[i]\n\t\t\t\t(src, dest) = (nearest[i], i)\n\t\ttotal_cost += min_cost\n\t\tcosts[dest] = inf\n\t\tif src == 0:\n\t\t\tbuild.append(dest)\n\t\telse:\n\t\t\tconnect.append('%d %d' % (src, dest))\n\t\tcurrent = dest\n\treturn (build, connect, total_cost)\nimport sys\nn = int(input())\npos = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]\nc_costs = list(map(int, input().split()))\nk_costs = list(map(int, input().split()))\ninf = 10 ** 18\nmatrix = [[inf] * (n + 1) for _ in range(n + 1)]\nfor i in range(n):\n\tfor j in range(i + 1, n):\n\t\tmatrix[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])\n\tmatrix[i + 1][0] = matrix[0][i + 1] = c_costs[i]\n(build, connect, cost) = prim(matrix)\nprint(cost)\nprint(len(build))\nprint(*build)\nprint(len(connect))\nif connect:\n\tprint(*connect, sep='\\n')\n", "def dist(a, b):\n\treturn abs(a[0] - b[0]) + abs(a[1] - b[1])\nn = int(input())\np = []\nfor i in range(n):\n\tp.append(list(map(int, input().split())))\nc = list(map(int, input().split()))\nk = list(map(int, input().split()))\nst = []\ned = []\nans = 0\nis_st = [1] * n\nparent = [-1] * n\nd = {i: c[i] for i in range(n)}\nfor i in range(n):\n\tm = min(d, key=d.get)\n\tif is_st[m]:\n\t\tst.append(m)\n\telse:\n\t\ted.append([m, parent[m]])\n\tans = ans + d[m]\n\tdel d[m]\n\tfor j in d.keys():\n\t\tt_cost = (k[m] + k[j]) * dist(p[m], p[j])\n\t\tif t_cost < d[j]:\n\t\t\td[j] = t_cost\n\t\t\tparent[j] = m\n\t\t\tis_st[j] = 0\nprint(ans)\nprint(len(st))\nfor i in st:\n\tprint(i + 1, end=' ')\nprint()\nprint(len(ed))\nfor i in ed:\n\tprint(i[0] + 1, i[1] + 1)\n", "def dis(x, y):\n\treturn abs(x[0] - y[0]) + abs(x[1] - y[1])\nn = int(input())\ncoor = []\nfor i in range(n):\n\t(x, y) = map(int, input().split())\n\tcoor.append([x, y])\ncost = list(map(int, input().split()))\nk = list(map(int, input().split()))\nd = {}\nfor i in range(n):\n\td[i] = cost[i]\nparent = [-1 for i in range(n + 1)]\nvisited = [0 for i in range(n + 1)]\nm = 0\nconnect = []\npower_set = []\n(ans, t) = (0, 0)\nfor i in range(n):\n\tm = min(d, key=d.get)\n\tif visited[m] == 1:\n\t\tconnect.append([m, parent[m]])\n\telse:\n\t\tpower_set.append(m)\n\tans += d[m]\n\tdel d[m]\n\tfor j in d.keys():\n\t\tt = dis(coor[j], coor[m]) * (k[j] + k[m])\n\t\tif t < d[j]:\n\t\t\td[j] = t\n\t\t\tparent[j] = m\n\t\t\tvisited[j] = 1\nprint(ans)\nprint(len(power_set))\nfor i in power_set:\n\tprint(i + 1, end=' ')\nprint()\nprint(len(connect))\nfor i in connect:\n\tprint(i[0] + 1, i[1] + 1)\n", "n = int(input())\ncord = [[*map(int, input().split())] for _ in range(n)]\nc = [*map(int, input().split())]\nk = [*map(int, input().split())]\nplant = set()\ncovered = set()\nparent = [-1] * n\nsum = 0\nfor _ in range(n):\n\t(cost, idx) = min(([cost, idx] for (idx, cost) in enumerate(c) if idx not in covered))\n\tsum += cost\n\tcovered.add(idx)\n\tif parent[idx] == -1:\n\t\tplant.add(idx)\n\tfor i in range(n):\n\t\tif i in covered:\n\t\t\tcontinue\n\t\tc_l = (k[i] + k[idx]) * (abs(cord[i][0] - cord[idx][0]) + abs(cord[i][1] - cord[idx][1]))\n\t\tif c_l < c[i]:\n\t\t\tc[i] = c_l\n\t\t\tparent[i] = idx\nprint('{}\\n{}'.format(sum, len(plant)))\nprint(*map(lambda x: x + 1, plant))\nlinks = 0\nout = ''\nfor (i, _) in enumerate(parent):\n\tif _ != -1:\n\t\tlinks += 1\n\t\tout += '\\n' + str(_ + 1) + ' ' + str(i + 1)\nprint(links, out)\n", "import sys\ninput = sys.stdin.readline\nn = int(input())\nX = [[0] * 7 for _ in range(n)]\nfor i in range(n):\n\t(x, y) = map(int, input().split())\n\t(X[i][0], X[i][1], X[i][2]) = (i + 1, x, y)\nC = [int(i) for i in input().split()]\nK = [int(i) for i in input().split()]\nfor i in range(n):\n\t(X[i][3], X[i][4]) = (C[i], K[i])\nans_am = 0\nans_ps = 0\nAns = []\nans_con = 0\nCon = []\n\ndef m(X):\n\tret = 0\n\tcur = X[0][3]\n\tfor i in range(1, len(X)):\n\t\tif X[i][3] < cur:\n\t\t\tret = i\n\t\t\tcur = X[i][3]\n\treturn ret\n\ndef cost(k, ki, x, xi, y, yi):\n\treturn (k + ki) * (abs(x - xi) + abs(y - yi))\nwhile X:\n\tr = m(X)\n\t(ind, x, y, c, k, flag, source) = X.pop(r)\n\tans_am += c\n\tif not flag:\n\t\tans_ps += 1\n\t\tAns.append(ind)\n\telse:\n\t\tans_con += 1\n\t\tCon.append((ind, source))\n\tfor i in range(len(X)):\n\t\t(indi, xi, yi, ci, ki, flagi, sourcei) = X[i]\n\t\tco = cost(k, ki, x, xi, y, yi)\n\t\tif co < ci:\n\t\t\t(X[i][3], X[i][5], X[i][6]) = (co, 1, ind)\nprint(ans_am)\nprint(ans_ps)\nprint(*Ans)\nprint(ans_con)\nfor (i, j) in Con:\n\tprint(i, j)\n", "import sys\nreader = (list(map(int, s.split())) for s in sys.stdin)\n(n,) = next(reader)\ncities = [None]\nfor _ in range(n):\n\t(x, y) = next(reader)\n\tcities.append((x, y))\ncs = [None] + list(next(reader))\nks = [None] + list(next(reader))\nn += 1\ng = [[None] * n for _ in range(n)]\nfor i in range(1, n):\n\tfor j in range(i + 1, n):\n\t\twire = ks[i] + ks[j]\n\t\tdist = abs(cities[i][0] - cities[j][0]) + abs(cities[i][1] - cities[j][1])\n\t\tg[i][j] = g[j][i] = wire * dist\nfor i in range(1, n):\n\tg[0][i] = g[i][0] = cs[i]\nfor i in range(n):\n\tg[i][i] = float('inf')\ntotalCost = 0\nstations = []\nconnections = []\nconnCosts = {i: float('inf') for i in range(n)}\nconnTo = [-1] * n\nstart = 0\nconnCosts[start] = 0\nwhile connCosts:\n\tv = min(connCosts, key=connCosts.get)\n\tif connCosts[v] == float('inf'):\n\t\tbreak\n\tfromNode = connTo[v]\n\tif not fromNode:\n\t\ttotalCost += g[v][fromNode]\n\t\tstations.append(v)\n\telif fromNode > 0:\n\t\ttotalCost += g[v][fromNode]\n\t\tconnections.append((v, fromNode))\n\tconnCosts.pop(v)\n\tfor (to, cost) in list(connCosts.items()):\n\t\tif g[v][to] < connCosts[to]:\n\t\t\tconnCosts[to] = g[v][to]\n\t\t\tconnTo[to] = v\nmyprint = sys.stdout.write\nmyprint(str(totalCost) + '\\n')\nmyprint(str(len(stations)) + '\\n')\n[myprint(str(st) + ' ') for st in stations]\nmyprint(str(len(connections)) + '\\n')\n[myprint(str(c1) + ' ' + str(c2) + '\\n') for (c1, c2) in connections]\n", "n = int(input())\nX = [[0] * 7 for _ in range(n)]\nfor i in range(n):\n\t(x, y) = map(int, input().split())\n\tX[i][0] = i + 1\n\tX[i][1] = x\n\tX[i][2] = y\nC = [int(i) for i in input().split()]\nK = [int(i) for i in input().split()]\nfor i in range(n):\n\tX[i][3] = C[i]\n\tX[i][4] = K[i]\nX.sort(key=lambda x: x[3])\nans_am = 0\nans_ps = 0\nAns = []\nans_con = 0\nCon = []\nwhile X:\n\t(ind, x, y, c, k, flag, source) = X.pop(0)\n\tans_am += c\n\tif flag == 0:\n\t\tans_ps += 1\n\t\tAns.append(ind)\n\telse:\n\t\tans_con += 1\n\t\tCon.append([ind, source])\n\tfor i in range(len(X)):\n\t\t(indi, xi, yi, ci, ki, flagi, sourcei) = X[i]\n\t\tif (k + ki) * (abs(x - xi) + abs(y - yi)) < ci:\n\t\t\tX[i][3] = (k + ki) * (abs(x - xi) + abs(y - yi))\n\t\t\tX[i][5] = 1\n\t\t\tX[i][6] = ind\n\tX.sort(key=lambda x: x[3])\nprint(ans_am)\nprint(ans_ps)\nprint(*Ans)\nprint(ans_con)\nfor (i, j) in Con:\n\tprint(i, j)\n", "import math\nn = int(input())\ncityNo = [0] * n\nfor i in range(n):\n\tcityNo[i] = list(map(int, input().split()))\ncost = list(map(int, input().split()))\nks = list(map(int, input().split()))\npowerStation = [0] * n\ntotalCost = 0\nreq_Powerstation = []\nnotReq_Powerstation = []\ntotalCost = 0\nestablished = {}\nupdated = [-1] * n\nfor j in range(n):\n\tcity = -1\n\tmini = 9999999999999999\n\tfor i in range(n):\n\t\tif mini > cost[i] and i not in established:\n\t\t\tcity = i\n\t\t\tmini = cost[i]\n\tif updated[city] == -1:\n\t\treq_Powerstation.append(city + 1)\n\telse:\n\t\tnotReq_Powerstation.append([city + 1, updated[city] + 1])\n\ttotalCost += cost[city]\n\testablished[city] = 1\n\tfor i in range(n):\n\t\tcost_From_City = (ks[i] + ks[city]) * (abs(cityNo[i][0] - cityNo[city][0]) + abs(cityNo[i][1] - cityNo[city][1]))\n\t\tif cost_From_City < cost[i]:\n\t\t\tcost[i] = cost_From_City\n\t\t\tupdated[i] = city\nprint(totalCost)\nprint(len(req_Powerstation))\nprint(*req_Powerstation)\nprint(len(notReq_Powerstation))\nfor i in range(len(notReq_Powerstation)):\n\tprint(*notReq_Powerstation[i])\n"]

difficulty: HARD

source: codeforces

raw_problem:
D. Shichikuji and Power Grid

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

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

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.

question:
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](1.png)
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.

tags: ['Graph algorithms', 'Shortest paths', 'Greedy algorithms', 'Tree algorithms', 'Spanning trees']

skill_types: ['Greedy algorithms']

raw_tags: ['greedy', 'shortest paths', 'dsu', 'trees', 'graphs']

data_split: test


D. The Beach

problem_index: D

time_limit: 1 second

memory_limit: 256 megabytes

note:
In the first example we can shift upper sunbed to the left and lower sunbed — to the right. Andrew will be able to put his sunbed vertically in the middle of the beach. We well cause $$$2 + 2 = 4$$$ units of discomfort. It is easy to prove that it is an optimal answer.
![image](images/cf_1753_D/7.png)![image](images/cf_1753_D/8.png)![image](images/cf_1753_D/9.png) Optimal strategy in the first example (Andrew's sunbed is colored white).

solutions: ["from sys import stdin\r\ninput=lambda :stdin.readline()[:-1]\r\n\r\nh,w=map(int,input().split())\r\np,q=map(int,input().split())\r\ns=[]\r\nfor _ in range(h):\r\n  s.append(input())\r\n\r\ndef conv(x,y):\r\n  return x*w+y\r\n\r\nedge=[[] for i in range(h*w)]\r\nstarts=[]\r\nfor x in range(h):\r\n  for y in range(w):\r\n    if s[x][y]=='.':\r\n      starts.append(conv(x,y))\r\n    if s[x][y]=='L':\r\n      for frm_x,frm_y,to_x,to_y in ((x,y-1,x,y+1),(x,y+2,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y+1,x,y),(x+1,y+1,x,y),(x-1,y,x,y+1),(x+1,y,x,y+1)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n    if s[x][y]=='U':\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y,x+1,y),(x+2,y,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x+1,y-1,x,y),(x+1,y+1,x,y),(x,y-1,x+1,y),(x,y+1,x+1,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n\r\nfrom heapq import heappush, heappop\r\nINF=10**15\r\ndef dijkstra(starts,n):\r\n  dist=[INF]*n\r\n  hq=[]\r\n  for s in starts:\r\n    heappush(hq,(0,s))\r\n    dist[s]=0\r\n  while hq:\r\n    w,v=heappop(hq)\r\n    if dist[v]<w:\r\n      continue\r\n    for to,cost in edge[v]:\r\n      if dist[v]+cost<dist[to]:\r\n        dist[to]=dist[v]+cost\r\n        heappush(hq,(dist[to],to))\r\n  return dist\r\n\r\ndist=dijkstra(starts,h*w)\r\ndist_mat=[[0]*w for i in range(h)]\r\nfor i in range(h):\r\n  for j in range(w):\r\n    dist_mat[i][j]=dist[conv(i,j)]\r\n\r\nans=INF\r\nfor x in range(h):\r\n  for y in range(w):\r\n    for dx,dy in ((0,1),(1,0)):\r\n      nx,ny=x+dx,y+dy\r\n      if 0<=nx<h and 0<=ny<w:\r\n        v = dist_mat[x][y]+dist_mat[nx][ny]\r\n        if v < ans: ans=v\r\n\r\nif ans>=INF:\r\n  print(-1)\r\nelse:\r\n  print(ans)", "from sys import stdin\r\ninput=lambda :stdin.readline()[:-1]\r\n\r\nh,w=map(int,input().split())\r\np,q=map(int,input().split())\r\ns=[]\r\nfor _ in range(h):\r\n  s.append(input())\r\n\r\ndef conv(x,y):\r\n  return x*w+y\r\n\r\nedge=[[] for i in range(h*w)]\r\nstarts=[]\r\nfor x in range(h):\r\n  for y in range(w):\r\n    if s[x][y]=='.':\r\n      starts.append(conv(x,y))\r\n    if s[x][y]=='L':\r\n      for frm_x,frm_y,to_x,to_y in ((x,y-1,x,y+1),(x,y+2,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y+1,x,y),(x+1,y+1,x,y),(x-1,y,x,y+1),(x+1,y,x,y+1)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n    if s[x][y]=='U':\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y,x+1,y),(x+2,y,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x+1,y-1,x,y),(x+1,y+1,x,y),(x,y-1,x+1,y),(x,y+1,x+1,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n\r\nfrom heapq import heappush, heappop\r\nINF=10**15\r\ndef dijkstra(starts,n):\r\n  dist=[INF]*n\r\n  hq=[]\r\n  for s in starts:\r\n    heappush(hq,(0,s))\r\n    dist[s]=0\r\n  while hq:\r\n    w,v=heappop(hq)\r\n    if dist[v]<w:\r\n      continue\r\n    for to,cost in edge[v]:\r\n      if dist[v]+cost<dist[to]:\r\n        dist[to]=dist[v]+cost\r\n        heappush(hq,(dist[to],to))\r\n  return dist\r\n\r\ndist=dijkstra(starts,h*w)\r\ndist_mat=[[0]*w for i in range(h)]\r\nfor i in range(h):\r\n  for j in range(w):\r\n    dist_mat[i][j]=dist[conv(i,j)]\r\n\r\nans=INF\r\nfor x in range(h):\r\n  for y in range(w):\r\n    for dx,dy in ((0,1),(1,0)):\r\n      nx,ny=x+dx,y+dy\r\n      if 0<=nx<h and 0<=ny<w:\r\n        ans=min(ans,dist_mat[x][y]+dist_mat[nx][ny])\r\n\r\nif ans>=INF:\r\n  print(-1)\r\nelse:\r\n  print(ans)", "from sys import stdin\r\ninput=lambda :stdin.readline()[:-1]\r\n\r\nh,w=map(int,input().split())\r\np,q=map(int,input().split())\r\ns=[]\r\nfor _ in range(h):\r\n  s.append(input())\r\n\r\ndef conv(x,y):\r\n  return x*w+y\r\n\r\nedge=[[] for i in range(h*w)]\r\nstarts=[]\r\nfor x in range(h):\r\n  for y in range(w):\r\n    if s[x][y]=='.':\r\n      starts.append(conv(x,y))\r\n    if s[x][y]=='L':\r\n      for frm_x,frm_y,to_x,to_y in ((x,y-1,x,y+1),(x,y+2,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y+1,x,y),(x+1,y+1,x,y),(x-1,y,x,y+1),(x+1,y,x,y+1)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n    if s[x][y]=='U':\r\n      for frm_x,frm_y,to_x,to_y in ((x-1,y,x+1,y),(x+2,y,x,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),q))\r\n      for frm_x,frm_y,to_x,to_y in ((x+1,y-1,x,y),(x+1,y+1,x,y),(x,y-1,x+1,y),(x,y+1,x+1,y)):\r\n        if 0<=frm_x<h and 0<=frm_y<w and 0<=to_x<h and 0<=to_y<w and s[frm_x][frm_y]!='#':\r\n          edge[conv(frm_x,frm_y)].append((conv(to_x,to_y),p))\r\n\r\nfrom heapq import heappush, heappop\r\nINF=10**15\r\ndef dijkstra(starts,n):\r\n  dist=[INF]*n\r\n  hq=[]\r\n  for s in starts:\r\n    heappush(hq,(0,s))\r\n    dist[s]=0\r\n  seen=[False]*n\r\n  while hq:\r\n    w,v=heappop(hq)\r\n    if dist[v]<w:\r\n      continue\r\n    seen[v]=True\r\n    for to,cost in edge[v]:\r\n      if seen[to]==False and dist[v]+cost<dist[to]:\r\n        dist[to]=dist[v]+cost\r\n        heappush(hq,(dist[to],to))\r\n  return dist\r\n\r\ndist=dijkstra(starts,h*w)\r\ndist_mat=[[0]*w for i in range(h)]\r\nfor i in range(h):\r\n  for j in range(w):\r\n    dist_mat[i][j]=dist[conv(i,j)]\r\n\r\nans=INF\r\nfor x in range(h):\r\n  for y in range(w):\r\n    for dx,dy in ((0,1),(1,0)):\r\n      nx,ny=x+dx,y+dy\r\n      if 0<=nx<h and 0<=ny<w:\r\n        ans=min(ans,dist_mat[x][y]+dist_mat[nx][ny])\r\n\r\nif ans>=INF:\r\n  print(-1)\r\nelse:\r\n  print(ans)", "inf = -1\r\n\r\ndef _min(a, b):\r\n    return a if b == inf or inf != a < b else b\r\n\r\nclass DistanceKeeper:\r\n    def __init__(self, n):\r\n        self.m = 1\r\n        while self.m < n: self.m *= 2\r\n        self.data = 2 * self.m * [inf]\r\n        self.dist = n * [inf]\r\n        self.__getitem__ = self.dist.__getitem__\r\n\r\n    def __setitem__(self, ind, x):\r\n        self.dist[ind] = x\r\n        ind += self.m\r\n        self.data[ind] = x\r\n        ind >>= 1\r\n        while ind:\r\n            self.data[ind] = _min(self.data[2 * ind], self.data[2 * ind + 1])\r\n            ind >>= 1\r\n\r\n\r\n    def __getitem__(self, ind):\r\n        return self.dist[ind]\r\n\r\n    def trav(self):\r\n        while self.data[1] != inf:\r\n            x = self.data[1]\r\n\r\n            ind = 1\r\n            while ind < self.m:\r\n                ind = 2 * ind + (self.data[2 * ind] != x)\r\n            ind -= self.m\r\n\r\n            self[ind] = inf\r\n            self.dist[ind] = x\r\n            yield ind\r\n\r\ndef dijkstra(graph, start):\r\n    n = len(graph)\r\n\r\n    P = [-1] * n\r\n    D = DistanceKeeper(n)\r\n    D[start] = 0\r\n\r\n    for node in D.trav():\r\n        for nei, weight in graph[node]:\r\n            new_dist = D[node] + weight\r\n            if D[nei] == inf or new_dist < D[nei]:\r\n                D[nei] = new_dist\r\n                P[nei] = node\r\n\r\n    return D.dist, P\r\n\r\n\r\nimport sys\r\ninput = sys.stdin.readline\r\n\r\nn, m = map(int, input().split())\r\nsz = n * m\r\np, q = map(int, input().split())\r\nb = [input().strip() for _ in range(n)]\r\n\r\nadj = [[] for _ in range(sz + 2)]\r\nso = sz\r\nsi = sz + 1\r\n\r\ndX = [-1, 1, 0, 0]\r\ndY = [0, 0, -1, 1,]\r\n\r\nfor i in range(n):\r\n    for j in range(m):\r\n        c = b[i][j]\r\n        if c == '.':\r\n            '''\r\n            if (i + j) % 2:\r\n                adj[so].append((m * i + j, 0))\r\n            else:\r\n                adj[m * i + j].append((si, 0))'''\r\n            adj[so].append((m * i + j, 0))\r\n        elif c == 'R':\r\n            assert j > 0\r\n            dest = m * i + (j - 1)\r\n            \r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, p))\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, q))\r\n        elif c == 'L':\r\n            assert j < m - 1\r\n            dest = m * i + (j + 1)\r\n            \r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, q))\r\n        elif c == 'U':\r\n            assert i < n - 1\r\n            dest = m * (i + 1) + j\r\n\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, p))\r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, q))\r\n        elif c == 'D':\r\n            assert i > 0\r\n            dest = m * (i - 1) + j\r\n\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, q))\r\n        else:\r\n            assert c == '#'\r\n\r\ndist, _ = dijkstra(adj, so)\r\nposs = []\r\n\r\n\r\nfor i in range(n):\r\n    for j in range(m):\r\n        if (i + j) % 2:\r\n            continue\r\n        if b[i][j] == '#':\r\n            continue\r\n\r\n        d1 = dist[m * i + j]\r\n        if d1 == -1:\r\n            continue\r\n\r\n        for d in range(4):\r\n            ii = i + dX[d]\r\n            jj = j + dY[d]\r\n\r\n            if 0 <= ii < n and 0 <= jj < m:\r\n                if b[ii][jj] == '#':\r\n                    continue\r\n                d2 = dist[m * ii + jj]\r\n                if d2 == -1:\r\n                    continue\r\n                \r\n                poss.append(d1 + d2)\r\n\r\nif poss:\r\n    print(min(poss))\r\nelse:\r\n    print(-1)", "inf = -1\r\n\r\ndef _min(a, b):\r\n    return a if b == inf or inf != a < b else b\r\n\r\nclass DistanceKeeper:\r\n    def __init__(self, n):\r\n        self.m = 1\r\n        while self.m < n: self.m *= 2\r\n        self.data = 2 * self.m * [inf]\r\n        self.dist = n * [inf]\r\n        self.__getitem__ = self.dist.__getitem__\r\n\r\n    def __setitem__(self, ind, x):\r\n        self.dist[ind] = x\r\n        ind += self.m\r\n        self.data[ind] = x\r\n        ind >>= 1\r\n        while ind:\r\n            self.data[ind] = _min(self.data[2 * ind], self.data[2 * ind + 1])\r\n            ind >>= 1\r\n\r\n\r\n    def __getitem__(self, ind):\r\n        return self.dist[ind]\r\n\r\n    def trav(self):\r\n        while self.data[1] != inf:\r\n            x = self.data[1]\r\n\r\n            ind = 1\r\n            while ind < self.m:\r\n                ind = 2 * ind + (self.data[2 * ind] != x)\r\n            ind -= self.m\r\n\r\n            self[ind] = inf\r\n            self.dist[ind] = x\r\n            yield ind\r\n\r\ndef dijkstra(graph, start):\r\n    n = len(graph)\r\n\r\n    P = [-1] * n\r\n    D = DistanceKeeper(n)\r\n    D[start] = 0\r\n\r\n    for node in D.trav():\r\n        for nei, weight in graph[node]:\r\n            new_dist = D[node] + weight\r\n            if D[nei] == inf or new_dist < D[nei]:\r\n                D[nei] = new_dist\r\n                P[nei] = node\r\n\r\n    return D.dist, P\r\n\r\n\r\nimport sys\r\ninput = sys.stdin.readline\r\n\r\nn, m = map(int, input().split())\r\nsz = n * m\r\np, q = map(int, input().split())\r\nb = [input().strip() for _ in range(n)]\r\n\r\nadj = [[] for _ in range(sz + 2)]\r\nso = sz\r\nsi = sz + 1\r\n\r\ndX = [-1, 1, 0, 0]\r\ndY = [0, 0, -1, 1,]\r\n\r\nfor i in range(n):\r\n    for j in range(m):\r\n        c = b[i][j]\r\n        if c == '.':\r\n            '''\r\n            if (i + j) % 2:\r\n                adj[so].append((m * i + j, 0))\r\n            else:\r\n                adj[m * i + j].append((si, 0))'''\r\n            adj[so].append((m * i + j, 0))\r\n        elif c == 'R':\r\n            assert j > 0\r\n            dest = m * i + (j - 1)\r\n            \r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, p))\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, q))\r\n        elif c == 'L':\r\n            assert j < m - 1\r\n            dest = m * i + (j + 1)\r\n            \r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, q))\r\n        elif c == 'U':\r\n            assert i < n - 1\r\n            dest = m * (i + 1) + j\r\n\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, p))\r\n            #From Up\r\n            if i > 0:\r\n                adj[m * (i - 1) + j].append((dest, q))\r\n        elif c == 'D':\r\n            assert i > 0\r\n            dest = m * (i - 1) + j\r\n\r\n            #From Right\r\n            if j < m - 1:\r\n                adj[m * i + (j + 1)].append((dest, p))\r\n            #From Left\r\n            if j > 0:\r\n                adj[m * i + (j - 1)].append((dest, p))\r\n            #From Down\r\n            if i < n - 1:\r\n                adj[m * (i + 1) + j].append((dest, q))\r\n        else:\r\n            assert c == '#'\r\n\r\ndist, _ = dijkstra(adj, so)\r\nposs = []\r\n\r\n\r\nfor i in range(n):\r\n    for j in range(m):\r\n        if (i + j) % 2:\r\n            continue\r\n        if b[i][j] == '#':\r\n            continue\r\n\r\n        d1 = dist[m * i + j]\r\n        if d1 == -1:\r\n            continue\r\n\r\n        for d in range(4):\r\n            ii = i + dX[d]\r\n            jj = j + dY[d]\r\n\r\n            if 0 <= ii < n and 0 <= jj < m:\r\n                if b[ii][jj] == '#':\r\n                    continue\r\n                d2 = dist[m * ii + jj]\r\n                if d2 == -1:\r\n                    continue\r\n                \r\n                poss.append(d1 + d2)\r\n\r\nif poss:\r\n    print(min(poss))\r\nelse:\r\n    print(-1)"]

source: codeforces

raw_problem:
D. The Beach

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Andrew loves the sea. That's why, at the height of the summer season, he decided to go to the beach, taking a sunbed with him to sunbathe.

The beach is a rectangular field with $$$n$$$ rows and $$$m$$$ columns. Some cells of the beach are free, some have roads, stones, shops and other non-movable objects. Some of two adjacent along the side cells can have sunbeds located either horizontally or vertically.

Andrew hopes to put his sunbed somewhere, but that's a bad luck, there may no longer be free places for him! That's why Andrew asked you to help him to find a free place for his sunbed. Andrew's sunbed also should be places on two adjacent cells.

If there are no two adjacent free cells, then in order to free some place for a sunbed, you will have to disturb other tourists. You can do the following actions:

 Come to some sunbed and, after causing $$$p$$$ units of discomfort to its owner, lift the sunbed by one of its sides and rotate it by $$$90$$$ degrees. One half of the sunbed must remain in the same cell and another half of the sunbed must move to the free cell. At the same time, anything could be on the way of a sunbed during the rotation .

 Rotation of the sunbed by $$$90$$$ degrees around cell $$$(1, 2)$$$.

 Come to some sunbed and, after causing $$$q$$$ units of discomfort to its owner, shift the sunbed along its long side by one cell. One half of the sunbed must move to the place of another, and another — to the free cell.

 Shift of the sunbed by one cell to the right.

In any moment each sunbed occupies two adjacent free cells. You cannot move more than one sunbed at a time.

Help Andrew to free a space for his sunbed, causing the minimum possible number of units of discomfort to other tourists, or detect that it is impossible.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — the number of rows and columns in rectangle.

The second line contains two integers $$$p$$$ and $$$q$$$ ($$$1 \le p, q \le 10^9$$$) — the number of units of discomfort caused by rotation and shift of a sunbed, respectively.

Each of the following $$$n$$$ lines contains $$$m$$$ characters, describing cells of the rectangle. Each lines consists of characters "L", "R", "D", "U", "." and "#", denoting the type of the cell. Characters "L", "R", "D" and "U" denote a half of a sunbed placed in the cell — left, right, bottom and top half, respectively. Character "." denotes a free cell and character "#" — a cell, occupied by some non-movable object.

Output

Print one integer — the minimum possible number of units of discomfort, caused to other tourists, to free a space for a sunbed. If it is impossible to free a space for a sunbed, print $$$-1$$$.

Examples

Input

2 5

5 2

.LR##

##LR.

Output

4

Input

2 3

4 5

LR.

#.#

Output

-1

Input

4 3

10 10

.LR

###

UU#

DD.

Output

-1

Input

3 6

10 7

.U##.#

#DLR##

.##LR.

Output

24

Note

In the first example we can shift upper sunbed to the left and lower sunbed — to the right. Andrew will be able to put his sunbed vertically in the middle of the beach. We well cause $$$2 + 2 = 4$$$ units of discomfort. It is easy to prove that it is an optimal answer.

 Optimal strategy in the first example (Andrew's sunbed is colored white).  In the second example it is impossible to free a space for Andrew's sunbed. All possible states of the beach after any rotates and shifts are illustrated in the problem statement.

question:
Andrew loves the sea. That's why, at the height of the summer season, he decided to go to the beach, taking a sunbed with him to sunbathe.
The beach is a rectangular field with $$$n$$$ rows and $$$m$$$ columns. Some cells of the beach are free, some have roads, stones, shops and other non-movable objects. Some of two adjacent along the side cells can have sunbeds located either horizontally or vertically.
Andrew hopes to put his sunbed somewhere, but that's a bad luck, there may no longer be free places for him! That's why Andrew asked you to help him to find a free place for his sunbed. Andrew's sunbed also should be places on two adjacent cells.
If there are no two adjacent free cells, then in order to free some place for a sunbed, you will have to disturb other tourists. You can do the following actions:
 -  Come to some sunbed and, after causing $$$p$$$ units of discomfort to its owner, lift the sunbed by one of its sides and rotate it by $$$90$$$ degrees. One half of the sunbed must remain in the same cell and another half of the sunbed must move to the free cell. At the same time, anything could be on the way of a sunbed during the rotation . ![image](1.png)![image](2.png)![image](3.png) Rotation of the sunbed by $$$90$$$ degrees around cell $$$(1, 2)$$$. -  Come to some sunbed and, after causing $$$q$$$ units of discomfort to its owner, shift the sunbed along its long side by one cell. One half of the sunbed must move to the place of another, and another — to the free cell. ![image](4.png)![image](5.png)![image](6.png) Shift of the sunbed by one cell to the right. In any moment each sunbed occupies two adjacent free cells. You cannot move more than one sunbed at a time.
Help Andrew to free a space for his sunbed, causing the minimum possible number of units of discomfort to other tourists, or detect that it is impossible.

Input
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 300\,000$$$, $$$1 \le n \cdot m \le 300\,000$$$) — the number of rows and columns in rectangle.
The second line contains two integers $$$p$$$ and $$$q$$$ ($$$1 \le p, q \le 10^9$$$) — the number of units of discomfort caused by rotation and shift of a sunbed, respectively.
Each of the following $$$n$$$ lines contains $$$m$$$ characters, describing cells of the rectangle. Each lines consists of characters "L", "R", "D", "U", "." and "#", denoting the type of the cell. Characters "L", "R", "D" and "U" denote a half of a sunbed placed in the cell — left, right, bottom and top half, respectively. Character "." denotes a free cell and character "#" — a cell, occupied by some non-movable object.

Output
Print one integer — the minimum possible number of units of discomfort, caused to other tourists, to free a space for a sunbed. If it is impossible to free a space for a sunbed, print $$$-1$$$.

Examples
Input
2 5
5 2
.LR##
##LR.

Output
4

Input
2 3
4 5
LR.
#.#

Output
-1

Input
4 3
10 10
.LR
###
UU#
DD.

Output
-1

Input
3 6
10 7
.U##.#
#DLR##
.##LR.

Output
24

Note
In the first example we can shift upper sunbed to the left and lower sunbed — to the right. Andrew will be able to put his sunbed vertically in the middle of the beach. We well cause $$$2 + 2 = 4$$$ units of discomfort. It is easy to prove that it is an optimal answer.
 ![image](7.png)![image](8.png)![image](9.png) Optimal strategy in the first example (Andrew's sunbed is colored white).  In the second example it is impossible to free a space for Andrew's sunbed. All possible states of the beach after any rotates and shifts are illustrated in the problem statement.

image_tags: Map Map Map Map Map Map Map Map Map

data_split: test


D. Spongebob and Squares

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.
![image](images/cf_599_D/1.png)
In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.
![image](images/cf_599_D/2.png)

solutions: ["n = int(input())\n(i, t, s) = [0] * 3\nr = []\nwhile 1 > 0:\n\ti += 1\n\tn -= i * i\n\tif n < 0:\n\t\tbreak\n\tt += i\n\tm = n // t\n\tif m * t != n:\n\t\tcontinue\n\tr.append((i, m + i))\n\tif m > 0:\n\t\tr.append((m + i, i))\nprint(len(r))\nr.sort()\nfor (m, n) in r:\n\tprint('%d %d' % (m, n))\n", "def solve(x):\n\tres = [(1, x)]\n\tif x != 1:\n\t\tres.append((x, 1))\n\t(index, a, b) = (1, 1, 0)\n\twhile True:\n\t\tb += a\n\t\tindex += 1\n\t\ta += index\n\t\tif a * index - b > x:\n\t\t\tbreak\n\t\tif (x + b) % a == 0:\n\t\t\tm = (x + b) // a\n\t\t\tres.append((index, m))\n\t\t\tif index != m:\n\t\t\t\tres.append((m, index))\n\tres.sort()\n\tprint(len(res))\n\tfor ares in res:\n\t\tprint(ares[0], ares[1])\n\ndef __starting_point():\n\tx = int(input())\n\tsolve(x)\n__starting_point()\n", "x = int(input()) * 6\n(n, equ, ans) = (0, False, [])\nwhile True:\n\tn += 1\n\tif n * (n + 1) * (2 * n - 1) > x:\n\t\tbreak\n\tif x % n != 0:\n\t\tcontinue\n\tif x % (n + 1) != 0:\n\t\tcontinue\n\tm = x // n // (n + 1) + n - 1\n\tif m % 3 != 0:\n\t\tcontinue\n\tm = m // 3\n\tif n <= m:\n\t\tans.append([n, m])\n\t\tif n == m:\n\t\t\tequ = True\nprint(len(ans) * 2 - equ)\nfor p in ans:\n\tprint('%d %d' % (p[0], p[1]))\nif equ:\n\tans.pop()\nans.reverse()\nfor p in ans:\n\tp.reverse()\n\tprint('%d %d' % (p[0], p[1]))\n", "from functools import reduce\nfrom itertools import islice, product\nfrom operator import mul\n\ndef prod(iterable, start=1):\n\treturn reduce(mul, iterable, start)\n\ndef isqrt(n):\n\t(x, px, nx) = (0, 0, n)\n\twhile nx not in (x, px):\n\t\t(px, x) = (x, nx)\n\t\tnx = (x + n // x) // 2\n\treturn min(x, nx)\n\ndef relevant_factors(n):\n\tfor i in range(2, 2000000):\n\t\tif i ** 2 > n:\n\t\t\tbreak\n\t\tc = 0\n\t\t(q, r) = divmod(n, i)\n\t\twhile not r:\n\t\t\tc += 1\n\t\t\tn = q\n\t\t\t(q, r) = divmod(n, i)\n\t\tif c:\n\t\t\tyield (i, c)\n\tif n > 1:\n\t\tsn = isqrt(n)\n\t\tif sn * sn == n:\n\t\t\tyield (sn, 2)\n\t\telif sn * (sn + 1) == n:\n\t\t\tyield ((sn, 1), (sn + 1, 1))\n\t\telse:\n\t\t\tyield (n, 1)\n\ndef divisors(fp):\n\treturn sorted((prod(t) for t in product(*[powers(f, e + 1) for (f, e) in fp])))\n\ndef powers(b, e):\n\tk = 1\n\tfor _ in range(e):\n\t\tyield k\n\t\tk *= b\n\ndef tables(n):\n\tif n == 1:\n\t\treturn [(1, 1)]\n\tt = set()\n\tn6 = 6 * n\n\tfor a in divisors(relevant_factors(n6)):\n\t\t(q, r) = divmod(n6, a * (a + 1))\n\t\tif r:\n\t\t\tcontinue\n\t\t(b, r) = divmod(q + a - 1, 3)\n\t\tif r:\n\t\t\tcontinue\n\t\tif b < a:\n\t\t\tcontinue\n\t\tt.add((a, b))\n\t\tt.add((b, a))\n\treturn sorted(t)\nn = int(input())\nts = tables(n)\nprint(len(ts))\nfor t in ts:\n\tprint('{} {}'.format(*t))\n", "s = int(input())\n(a, b) = ([], [])\nfor n in range(1, 1450000):\n\tu = 6 * s - n * (n - 1) * (n + n - 1) + 3 * (n - 1) * n * n\n\tv = 6 * n * n - 3 * (n - 1) * n\n\tif u % v == 0:\n\t\tu //= v\n\t\tif n <= u:\n\t\t\ta += [(n, u)]\n\t\t\tif n < u:\n\t\t\t\tb += [(u, n)]\n\t\telse:\n\t\t\tbreak\nprint(len(a) + len(b))\nfor e in a:\n\tprint(*e)\nfor e in reversed(b):\n\tprint(*e)\n", "(n, i, t, r) = (int(input()), 0, 0, [])\nwhile 1:\n\ti += 1\n\tn -= i * i\n\tif n < 0:\n\t\tbreak\n\tt += i\n\tm = n // t\n\tr += [(m + i, i), (i, m + i)][m == 0:] * (m * t == n)\nprint(len(r))\nfor p in sorted(r):\n\tprint('%d %d' % p)\n", "x = int(input())\n\ndef solve(x):\n\tcount = 0\n\tlst = []\n\tx6 = x * 6\n\tfor n in range(1, x + 1):\n\t\t(t, r) = divmod(x6, n * (n + 1))\n\t\tif t < 2 * n + 1:\n\t\t\tbreak\n\t\tif r:\n\t\t\tcontinue\n\t\t(m, r) = divmod(t + n - 1, 3)\n\t\tif r:\n\t\t\tcontinue\n\t\tcount += 2\n\t\tlst.append((n, m))\n\t(nn, mm) = lst[-1]\n\tif nn == mm:\n\t\tcount -= 1\n\tprint(count)\n\tfor (n, m) in lst:\n\t\tprint(n, m)\n\tif nn != mm:\n\t\tprint(mm, nn)\n\tlst.reverse()\n\tfor (n, m) in lst[1:]:\n\t\tprint(m, n)\nsolve(x)\n", "import itertools\nimport math\nx = int(input())\nkmax = math.floor((3 * x) ** (1 / 3))\nans = []\nfor i in range(1, kmax + 1):\n\tif 6 * x % (i * (i + 1)) == 0:\n\t\ts = 6 * x // (i * (i + 1)) + i - 1\n\t\tif s % 3 == 0:\n\t\t\tans.append((i, s // 3))\nres = 2 * len(ans) - 1 if ans[-1][0] == ans[-1][1] else 2 * len(ans)\nprint(res)\nfor pair in ans[:-1]:\n\tprint(pair[0], pair[1])\nif res % 2 == 0:\n\tprint(ans[-1][0], ans[-1][1])\nfor pair in reversed(ans):\n\tprint(pair[1], pair[0])\n", "x = int(input())\na = 1\nans = []\nt = set()\nwhile a * a * a <= 3 * x:\n\tif a in t:\n\t\tbreak\n\tif ((a * a * a - a) // 3 + 2 * x) % (a * a + a) == 0:\n\t\tb = ((a * a * a - a) // 3 + 2 * x) // (a * a + a)\n\t\tans.append([a, b])\n\t\tif a != b:\n\t\t\tans.append([b, a])\n\t\tt.add(a)\n\t\tt.add(b)\n\ta += 1\nprint(len(ans))\nans = sorted(ans, key=lambda student: student[0])\nfor i in ans:\n\tc = []\n\tc.append(str(i[0]))\n\tc.append(str(i[1]))\n\tprint(' '.join(c))\n", "from itertools import chain, combinations\nfrom functools import reduce\nfrom collections import defaultdict\n\ndef res(m, n):\n\tk = min(m, n)\n\treturn (1 + k) * (k + 2 * k ** 2 - 3 * k * (m + n) + 6 * m * n) // 6\n\ndef powerset(iterable):\n\ts = list(iterable)\n\treturn chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))\n\ndef prod(it):\n\tr = 1\n\tfor elem in it:\n\t\tr *= elem\n\treturn r\n\ndef factorGenerator(n):\n\tres = defaultdict(lambda : 0)\n\tfor p in range(2, 10 ** 6 + 1):\n\t\twhile n % p == 0:\n\t\t\tres[p] += 1\n\t\t\tn = n // p\n\treturn res\n\ndef divisorGen(n):\n\tfactors = list(factorGenerator(n).items())\n\tnfactors = len(factors)\n\tf = [0] * nfactors\n\twhile True:\n\t\tyield reduce(lambda x, y: x * y, [factors[x][0] ** f[x] for x in range(nfactors)], 1)\n\t\ti = 0\n\t\twhile True:\n\t\t\tf[i] += 1\n\t\t\tif f[i] <= factors[i][1]:\n\t\t\t\tbreak\n\t\t\tf[i] = 0\n\t\t\ti += 1\n\t\t\tif i >= nfactors:\n\t\t\t\treturn\n\ndef res2(x):\n\tr = []\n\tx6 = 6 * x\n\tdivisors = set(divisorGen(x6))\n\tfor m in divisors:\n\t\ta = x6 // m\n\t\tif a % (m + 1) != 0:\n\t\t\tcontinue\n\t\tb = a // (m + 1)\n\t\tc = b + m - 1\n\t\tif c % 3 != 0:\n\t\t\tcontinue\n\t\tn = c // 3\n\t\tif n < m:\n\t\t\tcontinue\n\t\tif res(m, n) != x:\n\t\t\tcontinue\n\t\tr.append((m, n))\n\treturn r\nx = int(input())\nr = res2(x)\nr = r + [(n, m) for (m, n) in r]\nr = sorted(set(r))\nprint(len(r))\nfor (m, n) in r:\n\tprint('%d %d' % (m, n))\n", "(p, q) = (int(input()), 1)\n(t, n) = ([], 1)\nwhile p > n * q:\n\tif p % q == 0:\n\t\tt.append((p // q, n))\n\tn += 1\n\tq += n\n\tp += (n * n - n) // 2\nt += [(m, n) for (n, m) in t]\nif p == n * q:\n\tt.append((n, n))\nprint(len(t))\nfor (n, m) in sorted(t):\n\tprint(n, m)\n", "import itertools as it\nimport functools\nimport operator\nimport collections\nimport math\nimport sys\n\ndef solve(x):\n\n\tdef find_p(n):\n\t\treturn (6 * x // (n * (n + 1)) - 2 * n - 1) // 3\n\n\tdef f(n, p):\n\t\treturn n * (n + 1) * (2 * n + 3 * p + 1) - 6 * x\n\tresult = []\n\tfor n in it.count(1):\n\t\tp = find_p(n)\n\t\tif p < 0:\n\t\t\tbreak\n\t\tif f(n, p) == 0:\n\t\t\tresult.append((n, n + p))\n\t\t\tif p > 0:\n\t\t\t\tresult.append((n + p, n))\n\tresult.sort()\n\treturn result\n\ndef main():\n\tx = int(input())\n\tresults = solve(x)\n\tprint(len(results))\n\tfor res in results:\n\t\tprint(*res)\nmain()\n", "def main():\n\tx = int(input())\n\tl = squares(x)\n\tlast = l[len(l) - 1]\n\tif last[0] != last[1]:\n\t\tprint(2 * len(l))\n\telse:\n\t\tprint(2 * len(l) - 1)\n\tfor pair in l:\n\t\tprint(pair[0], pair[1])\n\tif last[0] != last[1]:\n\t\tfor pair in l[::-1]:\n\t\t\tprint(pair[1], pair[0])\n\telse:\n\t\trevL = l[::-1]\n\t\tfor pair in revL[1:]:\n\t\t\tprint(pair[1], pair[0])\n\ndef squares(x):\n\tif x == 1:\n\t\treturn [(1, 1)]\n\tresult = []\n\tcubeRoot = int((6 * x) ** (1 / 3))\n\tn = 1\n\twhile n <= cubeRoot:\n\t\ty = 6 * x\n\t\ttemp = n * (n + 1)\n\t\tif y % temp == 0:\n\t\t\ty //= temp\n\t\t\ty += n - 1\n\t\t\tif y % 3 == 0:\n\t\t\t\tm = y // 3\n\t\t\t\tif m >= n:\n\t\t\t\t\tresult += [(n, m)]\n\t\tn += 1\n\treturn result\nmain()\n", "x = 6 * int(input())\nr = []\nfor m in range(1, 10 ** 7):\n\td = m * (m + 1)\n\tif d * m > x:\n\t\tbreak\n\tif x % d != 0:\n\t\tcontinue\n\tmx = x // d + m - 1\n\tif mx % 3 != 0:\n\t\tcontinue\n\tnx = mx // 3\n\tif nx > m:\n\t\tr.append((m, nx))\n\t\tr.append((nx, m))\n\telif nx == m:\n\t\tr.append((m, nx))\nprint(len(r))\nfor sol in sorted(r):\n\tprint(str(sol[0]) + ' ' + str(sol[1]))\n", "import unittest\nimport sys\n\nclass Squares:\n\n\tdef __init__(self, test_inputs=None):\n\t\tit = iter(test_inputs.split('\\n')) if test_inputs else None\n\n\t\tdef uinput():\n\t\t\treturn next(it) if it else sys.stdin.readline().rstrip()\n\t\t[self.n] = map(int, uinput().split())\n\n\tdef calculate(self):\n\t\tresult = []\n\t\tn = 1\n\t\twhile n * n * (n - 1) // 6 < self.n:\n\t\t\ta = n * (n + 1) // 2\n\t\t\tb = n * (n - 1) * (n + 1) // 6\n\t\t\tm = self.n + b\n\t\t\tk = m // a\n\t\t\tif n <= k and m % a == 0:\n\t\t\t\tresult.append((n, k))\n\t\t\tn += 1\n\t\tresult2 = list(result)\n\t\tresult2 += [(b, a) for (a, b) in reversed(result) if a != b]\n\t\ts = str(len(result2)) + '\\n'\n\t\ts += '\\n'.join([str(a) + ' ' + str(b) for (a, b) in result2])\n\t\treturn s\n\nclass unitTests(unittest.TestCase):\n\n\tdef test_single_test(self):\n\t\ttest = '26'\n\t\td = Squares(test)\n\t\tself.assertEqual(d.n, 26)\n\t\tself.assertEqual(Squares(test).calculate(), '6\\n1 26\\n2 9\\n3 5\\n5 3\\n9 2\\n26 1')\n\t\ttest = '0'\n\t\tself.assertEqual(Squares(test).calculate(), '0\\n')\n\t\ttest = ''\n\t\ttest = ''\n\n\tdef time_limit_test(self, nmax):\n\t\timport random\n\t\timport timeit\n\t\ttest = str(nmax) + ' ' + str(nmax) + '\\n'\n\t\tnumnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]\n\t\ttest += '\\n'.join(numnums) + '\\n'\n\t\tnums = [random.randint(1, 10000) for i in range(nmax)]\n\t\ttest += ' '.join(map(str, nums)) + '\\n'\n\t\tstart = timeit.default_timer()\n\t\td = Squares(test)\n\t\tcalc = timeit.default_timer()\n\t\td.calculate()\n\t\tstop = timeit.default_timer()\n\t\tprint('\\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))\nsys.setrecursionlimit(100000)\nif sys.argv[-1] == '-ut':\n\tunittest.main(argv=[' '])\nsys.stdout.write(Squares().calculate())\n", "x = int(input())\nif x == 1:\n\ta = [(1, 1)]\na = []\ncor = int((6 * x) ** (1 / 3))\nn = 1\nwhile n <= cor:\n\ty = 6 * x\n\ttec = n * (n + 1)\n\tif y % tec == 0:\n\t\ty //= tec\n\t\ty += n - 1\n\t\tif y % 3 == 0:\n\t\t\tm = y // 3\n\t\t\tif m >= n:\n\t\t\t\ta += [(n, m)]\n\tn += 1\np = a[len(a) - 1]\nif p[0] != p[1]:\n\tprint(2 * len(a))\nelse:\n\tprint(2 * len(a) - 1)\nfor i in a:\n\tprint(i[0], i[1])\nif p[0] != p[1]:\n\tfor i in a[::-1]:\n\t\tprint(i[1], i[0])\nelse:\n\tfor i in a[::-1][1:]:\n\t\tprint(i[1], i[0])\n", "n = int(input())\nans = []\nfor i in range(1, 1442250 + 10):\n\tt = i * (i + 1) // 2\n\t(j, mod) = divmod(n + (i - 1) * t // 3, t)\n\tif i > j:\n\t\tbreak\n\tif mod == 0:\n\t\tans.append((i, j))\n\t\tif i != j:\n\t\t\tans.append((j, i))\nans.sort()\nprint(len(ans))\nfor (x, y) in ans:\n\tprint(x, y)\n", "__author__ = 'MoonBall'\nimport sys\nT = 1\n\ndef process():\n\tans = []\n\tN = int(input())\n\tfor i in range(1, 3000000):\n\t\ta = N + i * (i - 1) * (i + 1) // 6\n\t\t(j, mod) = divmod(a, i * (i + 1) // 2)\n\t\tif i > j:\n\t\t\tbreak\n\t\tif mod:\n\t\t\tcontinue\n\t\tans.append((i, j))\n\t\tif i != j:\n\t\t\tans.append((j, i))\n\tans.sort()\n\tprint(len(ans))\n\tfor (i, j) in ans:\n\t\tprint(i, j)\nfor _ in range(T):\n\tprocess()\n", "n = int(input())\ni = 0\ns = 0\nt = 0\nx = 0\nf = 0\nres1 = []\nres2 = []\nwhile n >= 0:\n\ti = i + 1\n\tn = n - i * i\n\tif n < 0:\n\t\tbreak\n\tt = t + i\n\tm = n // t\n\tif m * t != n:\n\t\tcontinue\n\telse:\n\t\tres1.append(i)\n\t\tres2.append(m + i)\n\t\tx = x + 1\n\t\tif m == 0:\n\t\t\tf = 1\nprint(str(int(2 * x - f)))\nfor i in range(x):\n\tprint(str(int(res1[i])) + ' ' + str(int(res2[i])))\nres1.reverse()\nres2.reverse()\nfor i in range(x):\n\tif res1[i] != res2[i]:\n\t\tprint(str(int(res2[i])) + ' ' + str(int(res1[i])))\n", "x = int(input())\ni = 1\nnmList = []\nwhile True:\n\tif i * (i + 1) * (2 * i + 1) > 6 * x:\n\t\tbreak\n\tif 6 * x % (i * (i + 1)) == 0 and (6 * x // (i * (i + 1)) - (2 * i + 1)) % 3 == 0:\n\t\tnmList.append((i, i + (6 * x // (i * (i + 1)) - (2 * i + 1)) // 3))\n\ti += 1\nnumber = 0\nfor elem in nmList:\n\tif elem[0] != elem[1]:\n\t\tnumber += 2\n\telse:\n\t\tnumber += 1\nprint(number)\nfor elem in nmList:\n\tprint(str(elem[0]) + ' ' + str(elem[1]))\nfor i in range(len(nmList) - 1, -1, -1):\n\telem = nmList[i]\n\tif elem[0] == elem[1]:\n\t\tcontinue\n\tprint(str(elem[1]) + ' ' + str(elem[0]))\n", "x = int(input())\nres = []\nok = -1\nfor i in range(1, 3000001):\n\tm = i\n\ttmp = (m - 1) * (m + 1) * m // 6 + x\n\tif tmp * 2 % (m * (m + 1)) == 0:\n\t\tn = int(tmp * 2 // (m * (m + 1)))\n\t\tif n > m:\n\t\t\tres.append([i, n])\n\t\tif n == m and ok == -1:\n\t\t\tok = len(res)\n\t\t\tres.append([i, i])\nd = 0 if ok == -1 else 1\nprint(len(res) * 2 - d)\nfor i in range(len(res)):\n\tprint(str(res[i][0]) + ' ' + str(res[i][1]))\nfor i in range(len(res)):\n\tif len(res) - i - 1 != ok:\n\t\tprint(str(res[len(res) - i - 1][1]) + ' ' + str(res[len(res) - i - 1][0]))\n", "from collections import Counter\n\ndef mp():\n\treturn map(int, input().split())\n\ndef lt():\n\treturn list(map(int, input().split()))\n\ndef pt(x):\n\tprint(x)\n\ndef ip():\n\treturn input()\n\ndef it():\n\treturn int(input())\n\ndef sl(x):\n\treturn [t for t in x]\n\ndef spl(x):\n\treturn x.split()\n\ndef aj(liste, item):\n\tliste.append(item)\n\ndef bin(x):\n\treturn '{0:b}'.format(x)\n\ndef listring(l):\n\treturn ' '.join([str(x) for x in l])\n\ndef printlist(l):\n\tprint(' '.join([str(x) for x in l]))\nn = it()\nL = []\nR = []\nfor i in range(1, int((3 * n) ** (1 / 3)) + 1):\n\tif 6 * n % (i * (i + 1)) == 0:\n\t\tif (6 * n // (i * (i + 1)) + i - 1) % 3 == 0:\n\t\t\tt = (6 * n // (i * (i + 1)) + i - 1) // 3\n\t\t\tL.append([i, t])\n\t\t\tif i < t:\n\t\t\t\tR.insert(0, [t, i])\nresult = L + R\nprint(len(result))\nfor i in result:\n\tprintlist(i)\n"]

difficulty: HARD

source: codeforces

raw_problem:
D. Spongebob and Squares

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input

The first line of the input contains a single integer x (1 ≤ x ≤ 1018) — the number of squares inside the tables Spongebob is interested in.

Output

First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

Examples

Input

26

Output

6
1 26
2 9
3 5
5 3
9 2
26 1

Input

2

Output

2
1 2
2 1

Input

8

Output

4
1 8
2 3
3 2
8 1

Note

In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.

question:
Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input
The first line of the input contains a single integer x (1 ≤ x ≤ 10^{18}) — the number of squares inside the tables Spongebob is interested in.

Output
First print a single integer k — the number of tables with exactly x distinct squares inside.
Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

Examples
Input
26

Output
6
1 26
2 9
3 5
5 3
9 2
26 1

Input
2

Output
2
1 2
2 1

Input
8

Output
4
1 8
2 3
3 2
8 1

Note
In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.
 ![image](1.png) In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.
 ![image](2.png)

skill_types: ['Complete search']

image_tags:
2D Geometry
2D Geometry

data_split: test


C. Plumber

problem_index: C

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
For the first example, the initial configuration of the grid is as follows.
![image](images/cf_115_C/3.png)
The only two possible final non-leaking pipe configurations are as follows:
![image](images/cf_115_C/4.png)
![image](images/cf_115_C/5.png)
For the second example, the initial grid is already leaking, so there will be no final grid that is non-leaking.
For the final example, there's only one possible non-leaking final grid as follows.
![image](images/cf_115_C/6.png)

difficulty: HARD

source: codeforces

raw_problem:
C. Plumber

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Little John aspires to become a plumber! Today he has drawn a grid consisting of n rows and m columns, consisting of n × m square cells.

In each cell he will draw a pipe segment. He can only draw four types of segments numbered from 1 to 4, illustrated as follows:

Each pipe segment has two ends, illustrated by the arrows in the picture above. For example, segment 1 has ends at top and left side of it.

Little John considers the piping system to be leaking if there is at least one pipe segment inside the grid whose end is not connected to another pipe's end or to the border of the grid. The image below shows an example of leaking and non-leaking systems of size 1 × 2.

Now, you will be given the grid that has been partially filled by Little John. Each cell will either contain one of the four segments above, or be empty. Find the number of possible different non-leaking final systems after Little John finishes filling all of the empty cells with pipe segments. Print this number modulo 1000003 (106 + 3).

Note that rotations or flipping of the grid are not allowed and so two configurations that are identical only when one of them has been rotated or flipped either horizontally or vertically are considered two different configurations.

Input

The first line will contain two single-space separated integers n and m (1 ≤ n, m, n·m ≤ 5·105) — the number of rows and columns respectively. Then n lines follow, each contains exactly m characters — the description of the grid. Each character describes a cell and is either one of these:

 "1" - "4" — a pipe segment of one of four types as described above

 "." — an empty cell

Output

Print a single integer denoting the number of possible final non-leaking pipe systems modulo 1000003 (106 + 3). If there are no such configurations, print 0.

Examples

Input

2 2
13
..

Output

2

Input

3 1
1
4
.

Output

0

Input

2 2
3.
.1

Output

1

Note

For the first example, the initial configuration of the grid is as follows.

The only two possible final non-leaking pipe configurations are as follows:

For the second example, the initial grid is already leaking, so there will be no final grid that is non-leaking.

For the final example, there's only one possible non-leaking final grid as follows.

question:
Little John aspires to become a plumber! Today he has drawn a grid consisting of n rows and m columns, consisting of n × m square cells.
In each cell he will draw a pipe segment. He can only draw four types of segments numbered from 1 to 4, illustrated as follows:
 ![image](1.png) Each pipe segment has two ends, illustrated by the arrows in the picture above. For example, segment 1 has ends at top and left side of it.
Little John considers the piping system to be leaking if there is at least one pipe segment inside the grid whose end is not connected to another pipe's end or to the border of the grid. The image below shows an example of leaking and non-leaking systems of size 1 × 2.
 ![image](2.png) Now, you will be given the grid that has been partially filled by Little John. Each cell will either contain one of the four segments above, or be empty. Find the number of possible different non-leaking final systems after Little John finishes filling all of the empty cells with pipe segments. Print this number modulo 1000003 (10^{6} + 3).
Note that rotations or flipping of the grid are not allowed and so two configurations that are identical only when one of them has been rotated or flipped either horizontally or vertically are considered two different configurations.

Input
The first line will contain two single-space separated integers n and m (1 ≤ n, m, n·m ≤ 5·10^{5}) — the number of rows and columns respectively. Then n lines follow, each contains exactly m characters — the description of the grid. Each character describes a cell and is either one of these:
 -  "1" - "4" — a pipe segment of one of four types as described above -  "." — an empty cell
Output
Print a single integer denoting the number of possible final non-leaking pipe systems modulo 1000003 (10^{6} + 3). If there are no such configurations, print 0.

Examples
Input
2 2
13
..

Output
2

Input
3 1
1
4
.

Output
0

Input
2 2
3.
.1

Output
1

Note
For the first example, the initial configuration of the grid is as follows.
 ![image](3.png) The only two possible final non-leaking pipe configurations are as follows:
 ![image](4.png)  ![image](5.png) For the second example, the initial grid is already leaking, so there will be no final grid that is non-leaking.
For the final example, there's only one possible non-leaking final grid as follows.
 ![image](6.png)

image_tags: Patterns Patterns Patterns Patterns Patterns Patterns

data_split: test