题目描述

约翰有n头奶牛，每头奶牛有一部双卡双待的手机，并且有联动和移通两个手机号。

约翰了解到若干条关于奶牛们的信息，每条信息包含三个整数$u,v,l$。表示如果网速超过l，奶牛u和奶牛v的手机可以通过对应运营商建立通信。如果存在一组奶牛$x_1,x_2,...,x_k$，$k\ge 0$满足u和v可以通过同一运营商建立间接的连接$u->x_1->x_2->,...,->x_k->v$，那么u和v两头奶牛就可以进行视频通话。

约翰准备为奶牛们搭建两个通信基站，一个是联动公司的，一个是移通公司的。如果他花费L元建立基站，那么所有通过该公司通信的网速都能达到L。

约翰想知道，最少花费多少钱建立基站，才能使得至少K头奶牛之间，可以通过某个运营商直接或间接的建立视频通话？

如果无解，输出-1

输入格式

第一行输入四个整数$N,A,B,K$，表示奶牛头数，联动公司的连接数，移通公司的连接数，约翰的目标对数K。

其后A行，每行三个整数$u,v,l$代表一个连接

其后B行，每行三个整数$u,v,l$代表一个连接。

输出格式

输出一行一个整数，代表建立两个基站最小的费用和。

样例数据

input

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

output

33

样例解释：令$L_a = 3$,$L_b=30$,那么(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)可以通过A连接，(1,5)(2,6)(3,6)(2,3)可以通过B连接，总共9对不同的节点。

数据规模与约定

Subtask1(24pts) $N \le 2000$

Subtask2(20pts) 两个公司连接的点没有交集。

Subtask3(24pts) $0 \le A \le 10$

Subtask4(32pts) 无特殊限制

对于所有的数据，$1\le N \le 200000,0\le A,B \le 200000, 0 \le K \le N(N-1)/2, 1\le u,v \le N ,1 \le l \le 10^9$

时间限制：$3 \text {s}$

空间限制：$512 \text {MB}$