Problem Description

This problem is a translation from CCC 2018 S5 "Maximum Strategic Savings"

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

There are $N \times P$ bidirectional air routes. For each planet $e$ (where $1 \le e \le N$), there are $P$ air routes numbered from $1$ to $P$. The $i$-th air route connects cities $(e, a_i)$ and $(e, b_i)$, and requires a daily maintenance cost of $c_i$.

There are $M \times Q$ bidirectional ports. For all cities numbered $f$ (where $1 \le f \le M$), there are $Q$ ports numbered from $1$ to $Q$. The $j$-th port connects cities $(x_j, f)$ and $(y_j, f)$, and requires a daily maintenance cost of $z_j$.

Now, some ports and/or air routes need to be dismantled or canceled such that the cities remain connected, while maximizing the total savings in maintenance costs.

Input Format

The first line contains four integers: $N, M, P, Q$ $(0 \le N, M, P, Q \le 10^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 \le 10^8)$.

The following $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 data guarantees that all cities are pairwise connected, with possible duplicate edges or self-loops.

Output Format

Output a single integer representing the maximum daily savings in maintenance costs.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

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

Sample Output #2

41

Notes

Sample 2 Explanation

One possible optimal solution is to close the air routes between cities $(1, 1)$ and $(1, 1)$, $(2, 1)$ and $(2, 1)$, $(1, 1)$ and $(1, 2)$, $(1, 3)$ and $(1, 2)$, $(2, 3)$ and $(2, 2)$; and close the port between cities $(2, 3)$ and $(1, 3)$. This results in savings of $8 + 8 + 6 + 7 + 7 + 5 = 41$.

For $\frac{2}{15}$ of the data, $P, Q \le 100$, 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 data, $P, Q \le 200$;

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

For all data, $1 \le N, M, P, Q \le 10^5$.

见题面 Input 部分

见题面 Output 部分