Minimum Cost for Sufficient Communication

In CCOland, Mayor Jason wishes to install telephone lines between N households, numbered from 1 to N. There are two competing telephone companies: Keenan Mobile and Chris Home. Each company offers telephone packages at various levels. A telephone line provided by a company has an associated level. If you buy a telephone package at level \(l\) (with cost \(l\)) from that company, you can use all the telephone lines of that company with level \(\leq l\).

Two households can communicate if they are connected by a path consisting solely of telephone lines provided by the same company. Mayor Jason wants to purchase one telephone package from each company (i.e. one level \(l_a\) from Keenan Mobile and one level \(l_b\) from Chris Home) with the minimum total cost \(l_a+l_b\) such that there are at least \(K\) pairs of households that can communicate (via at least one of the companies).

You are given the details of the telephone lines provided by both companies. For each telephone line you are given its endpoints and its level. Determine the minimum total cost (i.e. \(l_a+l_b\)) needed to ensure that there are at least \(K\) pairs of households (\(i,j\) with \(i \neq j\)) that can communicate. If it is impossible to achieve, output -1.

Note: A household pair that is connected by both companies is only counted once.

inputFormat

The first line contains four integers: N, M1, M2 and K where:

• N is the number of households.
• M1 is the number of telephone lines offered by Keenan Mobile.
• M2 is the number of telephone lines offered by Chris Home.
• K is the minimum required number of communicating household pairs.

The next M1 lines each contain three integers: u v l, meaning that there is a telephone line between households u and v offered by Keenan Mobile with level l.

The following M2 lines each contain three integers in the same format, representing the telephone lines offered by Chris Home.

Remember, a telephone package purchased at level \(l\) (cost \(l\)) allows the use of all telephone lines from that company with level \(\leq l\).

outputFormat

Output a single integer: the minimum total cost (i.e. \(l_a+l_b\)) to ensure that at least \(K\) pairs of households can communicate (via one of the companies). If no such choice exists, output -1.

sample

3 2 1 1
1 2 1
2 3 2
1 3 2

1