题目描述

译自 CCO 2022 Day2 T2「Phone Plans」。

CCOland 的市长 Jason 想要在 $N$ 个住户之间安装电话线，这些住户从 $1$ 到 $N$ 编号。为此，他向两家竞争对手 Keenan 移动电话（简称 K 公司）和 Chris 家庭电话（简称 C 公司）询问了他们的电话套餐。

一个公司的电话套餐对应于一个特定的等级，每条电话线都有一个等级和与之相关的公司。如果你从一个公司购买了等级为 $l$ 的电话套餐，那么你就能够使用该公司所有等级小于或等于 $l$ 的电话线。等级为 $l$ 的电话套餐的价格为 $l$，你不能选择价格低于 $0$ 的电话套餐。

两个住户只有在通过同一家公司的电话线的路径连接时才能相互通信。Jason 想要从每家公司购买一个最低成本的电话套餐，使得至少有 $K$ 对不同的住户能够相互通信（同一对住户通过任意一家公司通信即计数，不重复统计）。

输入格式

第一行包含四个用空格分隔的整数 $N, A, B, K$，分别表示：

• $N$：住户的数量；
• $A$：K 公司的电话线数量；
• $B$：C 公司的电话线数量；
• $K$：需要能够相互通信的最小住户对数。

接下来的 $A$ 行，每行包含三个用空格分隔的整数 $u, v$ 和 $l$，表示一条 K 公司的电话线：

• 连接住户 $u$ 和 $v$（$1 \leq u, v \leq N$）；
• 等级为 $l$（$1 \leq l \leq 10^9$）。

接下来的 $B$ 行，每行包含三个用空格分隔的整数 $u, v$ 和 $l$，表示一条 C 公司的电话线：

• 连接住户 $u$ 和 $v$（$1 \leq u, v \leq N$）；
• 等级为 $l$（$1 \leq l \leq 10^9$）。

输出格式

输出连接至少 $K$ 对不同住户所需的最低成本（即 K 公司套餐价格 + C 公司套餐价格）。如果不可能（即使购买两家公司的最高等级套餐，通信对数仍不足 $K$），则输出 $-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

输出

33

样例解释

• 选择 K 公司等级 $3$ 的套餐（价格 $3$）：可使用等级 $\leq 3$ 的电话线，形成连通分量 $\{1,2,3,4\}$，通信对数为 $\binom{4}{2} = 6$ 对（$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$）。
• 选择 C 公司等级 $30$ 的套餐（价格 $30$）：可使用等级 $\leq 30$ 的电话线，形成连通分量 $\{1,2,3,5,6\}$，新增通信对数为 $3$ 对（$(1,5),(2,6),(3,6)$），与 K 公司的对数无重复。
• 总通信对数 $6 + 3 = 9$，满足 $K=9$，总成本 $3 + 30 = 33$，为最低成本。

数据范围与提示

对于所有的数据，有：

• $1 \leq N \leq 2 \times 10^5$；
• $0 \leq A, B \leq 2 \times 10^5$；
• $0 \leq K \leq \frac{N(N-1)}{2}$（$\binom{N}{2}$ 为所有住户对的总数）。

详细子任务附加限制及分值如下表所示：