Thanks to the Doctor's help, the rebels managed to steal enough gold to launch a full-scale attack on the Empire! However, Darth Vader is looking for revenge and wants to take back his gold.

The rebels have hidden the gold in various bases throughout the galaxy. Darth Vader and the Empire are looking to send out their spaceships to attack these bases.

The galaxy can be represented as an undirected graph with $n$ planets (nodes) and $m$ wormholes (edges), each connecting two planets.

A total of $s$ empire spaceships and $b$ rebel bases are located at different planets in the galaxy.

Each spaceship is given a location $x$, denoting the index of the planet on which it is located, an attacking strength $a$, and a certain amount of fuel $f$.

Each base is given a location $x$, and a defensive strength $d$.

A spaceship can attack a base if both of these conditions hold:   the spaceship's attacking strength is greater or equal than the defensive strength of the base  the spaceship's fuel is greater or equal to the shortest distance, computed as the number of wormholes, between the spaceship's planet and the base's planet 

Vader is very particular about his attacking formations. He requires that each spaceship is to attack at most one base and that each base is to be attacked by at most one spaceship.

Vader knows that the rebels have hidden $k$ gold in each base, so he will assign the spaceships to attack bases in such a way that maximizes the number of bases attacked.

Therefore, for each base that is attacked, the rebels lose $k$ gold.

However, the rebels have the ability to create any number of dummy bases. With the Doctor's help, these bases would exist beyond space and time, so all spaceship can reach them and attack them. Moreover, a dummy base is designed to seem irresistible: that is, it will always be attacked by some spaceship.

Of course, dummy bases do not contain any gold, but creating such a dummy base costs $h$ gold.

What is the minimum gold the rebels can lose if they create an optimal number of dummy bases?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 100$, $0 \leq m \leq 10000$), the number of nodes and the number of edges, respectively.

The next $m$ lines contain two integers $u$ and $v$ ($1 \leq u$, $v \leq n$) denoting an undirected edge between the two nodes.

The next line contains four integers $s$, $b$, $k$ and $h$ ($1 \leq s$, $b \leq 1000$, $0 \leq k$, $h \leq 10^9$), the number of spaceships, the number of bases, the cost of having a base attacked, and the cost of creating a dummy base, respectively.

The next $s$ lines contain three integers $x$, $a$, $f$ ($1 \leq x \leq n$, $0 \leq a$, $f \leq 10^9$), denoting the location, attack, and fuel of the spaceship.

The next $b$ lines contain two integers $x$, $d$ ($1 \leq x \leq n$, $0 \leq d \leq 10^9$), denoting the location and defence of the base.


-----Output-----

Print a single integer, the minimum cost in terms of gold.


-----Example-----
Input
6 7
1 2
2 3
3 4
4 6
6 5
4 4
3 6
4 2 7 3
1 10 2
3 8 2
5 1 0
6 5 4
3 7
5 2

Output
12



-----Note-----

One way to minimize the cost is to build $4$ dummy bases, for a total cost of $4 \times 3 = 12$.

One empire spaceship will be assigned to attack each of these dummy bases, resulting in zero actual bases attacked.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Graph algorithms

Flows and cuts

Shortest paths


Solutions:
def naiveSolve():
	return

def floyd_warshall(n, edges):
	dist = [[0 if i == j else float('inf') for i in range(n)] for j in range(n)]
	for (u, v, d) in edges:
		dist[u][v] = d
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dist[i][k] + dist[k][j] < dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
	return dist

def hopcroft_karp(graph, n, m):
	assert n == len(graph)
	match1 = [-1] * n
	match2 = [-1] * m
	for node in range(n):
		for nei in graph[node]:
			if match2[nei] == -1:
				match1[node] = nei
				match2[nei] = node
				break
	while 1:
		bfs = [node for node in range(n) if match1[node] == -1]
		depth = [-1] * n
		for node in bfs:
			depth[node] = 0
		for node in bfs:
			for nei in graph[node]:
				next_node = match2[nei]
				if next_node == -1:
					break
				if depth[next_node] == -1:
					depth[next_node] = depth[node] + 1
					bfs.append(next_node)
			else:
				continue
			break
		else:
			break
		pointer = [len(c) for c in graph]
		dfs = [node for node in range(n) if depth[node] == 0]
		while dfs:
			node = dfs[-1]
			while pointer[node]:
				pointer[node] -= 1
				nei = graph[node][pointer[node]]
				next_node = match2[nei]
				if next_node == -1:
					while nei != -1:
						node = dfs.pop()
						(match2[nei], match1[node], nei) = (node, nei, match1[node])
					break
				elif depth[node] + 1 == depth[next_node]:
					dfs.append(next_node)
					break
			else:
				dfs.pop()
	return (match1, match2)

def main():
	(n, m) = readIntArr()
	adj = [set() for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = readIntArr()
		adj[u].add(v)
		adj[v].add(u)
	(s, b, k, h) = readIntArr()
	ships = []
	for _ in range(s):
		(loc, atk, fuel) = readIntArr()
		ships.append((loc, atk, fuel))
	bases = []
	for _ in range(b):
		(loc, deff) = readIntArr()
		bases.append((loc, deff))
	edges = []
	for u in range(1, n + 1):
		for v in adj[u]:
			if u != v:
				edges.append((u, v, 1))
	dist = floyd_warshall(n + 1, edges)
	graph = [[] for _ in range(s)]
	for ship in range(s):
		for base in range(b):
			(ls, atk, fuel) = ships[ship]
			(lb, deff) = bases[base]
			if atk >= deff and fuel >= dist[ls][lb]:
				graph[ship].append(base)
	(match1, match2) = hopcroft_karp(graph, s, b)
	matchCnts = 0
	for v in match1:
		if v != -1:
			matchCnts += 1
	zeroDummiesCost = k * matchCnts
	shipsDummiesCost = h * s
	print(min(zeroDummiesCost, shipsDummiesCost))
	return
import sys
input = sys.stdin.buffer.readline

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

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

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

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

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

def queryInteractive(r):
	print('? {}'.format(r))
	sys.stdout.flush()
	return readIntArr()

def answerInteractive(adj, n):
	print('!')
	for u in range(1, n + 1):
		for v in adj[u]:
			if v > u:
				print('{} {}'.format(u, v))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys

def matching(node, visited, adj, assigned):
	if node == -1:
		return True
	if visited[node]:
		return False
	visited[node] = True
	for neighbor in adj[node]:
		if matching(assigned[neighbor], visited, adj, assigned):
			assigned[neighbor] = node
			return True
	return False
INF = 1000 * 1000
inp = [int(x) for x in sys.stdin.read().split()]
(n, m) = (inp[0], inp[1])
inp_idx = 2
G = [[INF] * n for _ in range(n)]
for _ in range(m):
	(a, b) = (inp[inp_idx] - 1, inp[inp_idx + 1] - 1)
	inp_idx += 2
	G[a][b] = G[b][a] = 1
for v in range(n):
	G[v][v] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])
(s, b, k, h) = (inp[inp_idx], inp[inp_idx + 1], inp[inp_idx + 2], inp[inp_idx + 3])
inp_idx += 4
spaceships = []
for _ in range(s):
	(x, a, f) = (inp[inp_idx] - 1, inp[inp_idx + 1], inp[inp_idx + 2])
	inp_idx += 3
	spaceships.append((x, a, f))
bases = []
for _ in range(b):
	(x, d) = (inp[inp_idx] - 1, inp[inp_idx + 1])
	inp_idx += 2
	bases.append((x, d))
adj = [[] for _ in range(s)]
assigned = [[] for _ in range(b)]
for i in range(s):
	space = spaceships[i]
	for j in range(b):
		base = bases[j]
		(u, v) = (space[0], base[0])
		fuel = space[2]
		if G[u][v] <= fuel and space[1] >= base[1]:
			adj[i].append(j)
visited = [False] * s
assigned = [-1] * b
matched = 0
for i in range(s):
	visited = [False] * s
	if matching(i, visited, adj, assigned):
		matched += 1
print(min(matched * k, h * s))