Maximum Strategic Savings

This problem is adapted 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 the \(f\)th city on planet \(e\) by \((e, f)\).

There are \(N \times P\) bidirectional flight routes. For each planet \(e\) \((1 \le e \le N)\) there are \(P\) flights. The \(i\)th flight on any planet connects cities \((e, a_i)\) and \((e, b_i)\) and costs \(c_i\) per day to maintain.

There are also \(M \times Q\) bidirectional port links. For every city index \(f\) \((1 \le f \le M)\) there are \(Q\) ports. The \(j\)th port connects cities \((x_j, f)\) and \((y_j, f)\) and costs \(z_j\) per day to maintain.

Your task is to cancel some flights and/or remove some port links so that the entire network of cities remains connected and the sum of the maintenance costs saved is maximized.

This is equivalent to removing a set of edges (flights and ports) such that the remaining network is a spanning tree (or spanning forest, which in a connected graph will be a tree), hence the maximum saving equals the total maintenance cost of all edges minus the cost of a minimum spanning tree (MST). The formulas used are:

Total Cost = \(\sum (\mbox{cost of all flights}) + \sum (\mbox{cost of all ports})\)

MST Cost = minimal cost required to connect all \(N\times M\) cities

Maximum Savings = Total Cost \( - \) MST Cost

inputFormat

The first line contains four integers \(N\), \(M\), \(P\), and \(Q\).

The next \(P\) lines each contain three integers \(a_i\), \(b_i\) and \(c_i\) describing the flights. Note that these \(P\) flights are available on each of the \(N\) planets.

The following \(Q\) lines each contain three integers \(x_j\), \(y_j\) and \(z_j\) describing the port links. Note that these \(Q\) ports are available for every city index from \(1\) to \(M\).

outputFormat

Output a single integer, which is the maximum saving (i.e. the total maintenance cost saved by canceling the appropriate flights and/or removing the appropriate port links while keeping the network connected).

sample

2 2 1 1
1 2 3
1 2 1

3