Problem Description

Jason, the mayor of CCOland, wants to install phone lines between $N$ households, numbered from $1$ to $N$. To do this, he asked two competing companies, Keenan Mobile and Chris Home Phone, about their phone plans. A phone plan from a company corresponds to a specific level; each phone line has a level and an associated company. If you buy a phone plan of level $l$ from a company, then you can use all phone lines of that company whose levels are less than or equal to $l$. The cost of a level $l$ plan is $l$, and you cannot choose a plan with cost less than $0$.

Two households can communicate with each other only if they are connected by a path consisting of phone lines from the same company. Jason wants to buy one lowest-cost phone plan from each company, so that at least $K$ distinct pairs of households can communicate with each other.

Input Format

The first line contains four space-separated integers $N$, $A$, $B$, and $K$, representing the number of households, the number of phone lines from Keenan Mobile, the number of phone lines from Chris Home Phone, and the minimum number of household pairs that must be able to communicate.

The next $A$ lines each contain three space-separated integers $u$, $v$, and $l$, describing a Keenan Mobile phone line. It connects households $u$ and $v$ $(1 \leq u, v \leq N)$ and has level $l$ $(1 \leq l \leq 10^{9})$.

The next $B$ lines each contain three space-separated integers $u$, $v$, and $l$, describing a Chris Home Phone line. It connects households $u$ and $v$ $(1 \leq u, v \leq N)$ and has level $l$ $(1 \leq l \leq 10^{9})$.

Output Format

Output the minimum total cost required to make at least $K$ distinct pairs of households connected. If it is impossible, output $-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

Hint

Sample Explanation

If Jason buys a level $3$ plan from Keenan Mobile and a level $30$ plan from Chris Home Phone, then $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ can communicate with each other through Keenan Mobile lines, and $(1,5),(2,6),(3,6),(2,3)$ can communicate with each other through Chris Home Phone lines. There is no cheaper way.

Constraints

For all testdata, $1 \leq N \leq 2\times 10^5$, $0 \leq A, B \leq 2\times 10^5$, and $0 \leq K \leq \frac{N(N-1)}{2}$.

Input Format

Output Format

Hint

Translated by ChatGPT 5