CCOland 的市长 Jason 想要在 $N$ 个住户之间安装电话线，住户编号为 $1$ 到 $N$。为此，他向两家竞争公司 Keenan Mobile Phones 和 Chris Home Telephone 咨询了电话套餐。每家公司的电话套餐对应一个特定的等级，且每条电话线都关联着一个等级和一家公司。如果你购买了某家公司等级为 $l$ 的套餐，你就可以使用该公司所有等级小于或等于 $l$ 的电话线。等级为 $l$ 的电话套餐费用为 $\$l$，且你不能选择费用低于 $\$0$ 的套餐。
两个住户只有在通过同一家公司的电话线路径相连时才能互相通信。Jason 希望以最小的总费用从每家公司各购买一个电话套餐，使得至少有 $K$ 对不同的住户能够互相通信。
输入格式
第一行包含四个空格分隔的整数 $N, A, B$ 和 $K$，分别代表住户数量、Keenan Mobile Phones 的电话线数量、Chris Home Telephone 的电话线数量以及需要能够互相通信的最小住户对数。
接下来的 $A$ 行，每行包含三个空格分隔的整数 $u, v$ 和 $l$，代表一条连接住户 $u$ 和 $v$ ($1 \le u, v \le N$) 的 Keenan Mobile Phones 电话线，其等级为 $l$ ($1 \le l \le 10^9$)。
接下来的 $B$ 行格式与前 $A$ 行相同，但代表的是 Chris Home Telephone 的电话线。
数据范围
| 分值 | $N$ 的范围 | $A$ 和 $B$ 的范围 | $K$ 的范围 | 附加限制 |
|---|---|---|---|---|
| 6 分 | $1 \le N \le 2000$ | $0 \le A, B \le 200\,000$ | $0 \le K \le \frac{N(N-1)}{2}$ | 无 |
| 5 分 | $1 \le N \le 200\,000$ | $0 \le A, B \le 200\,000$ | $0 \le K \le \frac{N(N-1)}{2}$ | Keenan Mobile Phones 仅连接奇数编号住户；Chris Home Telephone 仅连接偶数编号住户 |
| 6 分 | $1 \le N \le 200\,000$ | $0 \le A \le 10$; $0 \le B \le 200\,000$ | $0 \le K \le \frac{N(N-1)}{2}$ | 无 |
| 8 分 | $1 \le N \le 200\,000$ | $0 \le A, B \le 200\,000$ | $0 \le K \le \frac{N(N-1)}{2}$ | 无 |
输出格式
输出连接至少 $K$ 对不同住户所需的最少费用，如果无法实现，则输出 $-1$。
样例
输入格式 1
6 4 4 9 1 2 1 2 3 2 1 4 3 3 4 4 5 6 40 1 5 30 2 6 20 3 6 10
输出格式 1
33
说明
对于每家公司，考虑以下住户通过电话线连接的方式：
如果 Jason 购买了 Keenan Mobile Phones 等级为 $3$ 的套餐和 Chris Home Telephone 等级为 $30$ 的套餐，那么 $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$ 可以通过 Keenan Mobile Phones 的线路通信，$(1, 5), (2, 6), (3, 6), (2, 3)$ 可以通过 Chris Home Telephone 的线路通信。没有更便宜的方法。