Problem Description

This problem is translated from CCC 2018 S5 “Maximum Strategic Savings”.

There are $N$ planets, numbered $1\ldots N$. Each planet has $M$ cities, numbered $1\ldots M$. We denote city $f$ on planet $e$ as $(e,\,f)$.

There are $N\times P$ undirected flight routes. For each planet $e(1\le e\le N)$, there are $P$ routes, numbered from $1$ to $P$. Route $i$ connects cities $(e,\,a_i)$ and $(e,\,b_i)$, and it costs $c_i$ per day to maintain.

There are $M\times Q$ undirected ports. For every city index $f(1\le f\le M)$, there are $Q$ ports, numbered from $1$ to $Q$. Port $j$ can connect cities $(x_j,\,f)$ and $(y_j,\,f)$, and it costs $z_j$ per day to maintain.

Now you need to remove some ports and/or cancel some flight routes such that all cities are still connected, and the total saved cost is maximized.

Input Format

The first line contains four integers $N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)$.

The next $P$ lines each contain three integers $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$.

The next $Q$ lines each contain three integers $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$.

The testdata guarantees that all cities are connected to each other. There may be multiple edges or self-loops.

Output Format

Output one integer on a single line, representing the maximum total cost that can be saved per day.

2 2 1 2
1 2 1
2 1 1
2 1 1

3

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

41

Hint

Explanation for Sample 2

One possible optimal solution is to close the flight routes between cities $(1,\,1)$ and $(1,1)$, $(2,\,1)$ and $(2,\,1)$, $(1,\,1)$ and $(1,\,2)$, $(1,\,3)$ and $(1,\,2)$, and $(2,\,3)$ and $(2,\,2)$; and close the port between cities $(2,\,3)$ and $(1,\,3)$. In the end, you can save a cost of $8 + 8 + 6 + 7 + 7 + 5 = 41$.

For $\frac{2}{15}$ of the testdata, $P,\,Q\le100$, and for all $1\le i\le P$, $c_i=1$; for all $1\le j\le Q$, $z_j=1$.

For another $\frac{2}{15}$ of the testdata, $P,\,Q\le 200$.

For another $\frac{5}{15}$ of the testdata, $N,\,M\le 200$.

For all testdata, $1\le N,\,M,\,P,\,Q\le10^5$.

Translated by ChatGPT 5