You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 CCC 2018 S5「Maximum Strategic Savings」

有 $N$ 个星球，编号为 $1\ldots N$。每个星球有 $M$ 座城市，编号为 $1\ldots M$。我们将 $e$ 星球上的城市 $f$ 记作 $(e,\,f)$。

有 $N\times P$ 条双向航线，对于每个星球 $e(1\le e\le N)$，有 $P$ 条航线，编号为 $1$ 到 $P$。第 $i$ 条航线连接城市 $(e,\,a_i)$ 和 $(e,\,b_i)$，且每天需要花费 $c_i$ 的代价维护。

有 $M\times Q$ 个双向港口。对于所有编号为 $f(1\le f\le M)$ 的城市，有 $Q$ 个港口，编号为 $1$ 到 $Q$。第 $j$ 个港口可以连接城市 $(x_j,\,f)$ 和 $(y_j,\,f)$，且每天需要花费 $z_j$ 的代价维护。

现在需要拆除一些港口和（或）取消一些航线，使得城市之间仍能保持联通，且节省的代价之和最大。

输入格式

第一行四个整数，分别为 $N,\,M,\,P,\,Q\ (0\le N,\,M,\,P,\,Q\le10^5)$。

接下来 $P$ 行，每行三个整数 $a_i,\,b_i,\,c_i(1\le a_i,\,b_i\le M,\,1\le c_i\le10^8)$。

再接下来 $Q$ 行，每行三个整数 $x_j,\,y_j,\,z_j(1\le x_j,\,y_j\le N,\,1\le z_j\le 10^8)$。

数据保证城市之间两两联通，可能有重边或自环。

输出格式

输出一行一个整数表示每天最多能节省的代价之和。

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

提示

样例 2 解释

一种可行的最优解是关闭城市 $(1,\,1)$ 与 $(1,1)$、$(2,\,1)$ 与 $(2,\,1)$、$(1,\,1)$ 与 $(1,\,2)$、$(1,\,3)$ 与 $(1,\,2)$、$(2,\,3)$ 与 $(2,\,2)$ 之间的航线；并关闭城市 $(2,\,3)$ 与 $(1,\,3)$ 间的港口。最终可以节省 $8 + 8 + 6 + 7 + 7 + 5 = 41$ 的代价。

对于 $\frac{2}{15}$ 的数据，$P,\,Q\le100$，且对于所有的 $1\le i\le P$，都有 $c_i=1$；对于所有的 $1\le j\le Q$，都有 $z_j=1$；

对于另外 $\frac{2}{15}$ 的数据，$P,\,Q\le 200$；

对于另外 $\frac{5}{15}$ 的数据，$N,\,M\le 200$；

对于全部的数据，$1\le N,\,M,\,P,\,Q\le10^5$。