Canadian Computing Olympiad: 2022 Day 2, Problem 2

The mayor of CCOland, Jason, wants to install telephone lines amongst ~N~ households, which are numbered from ~1~ to ~N~. To do so, he has asked two rivalling companies, Keenan Mobile Phones and Chris Home Telephone, for their phone plans. A phone plan for a company corresponds to a certain level, and every telephone line has a level and company associated with it. If you have purchased a phone plan from a company with level ~l~, then you are able to use all the telephone lines whose level is less than or equal to ~l~ that is associated with that company. A phone plan of level ~l~ costs ~\$l~, and you cannot pick a phone plan of less than ~\$0~.

Two households can only communicate with each other if they are connected by a path of telephone lines of the same company. Jason would like to buy one phone plan from each company of minimal cost such that there are at least ~K~ different pairs of households that can communicate with each other.

Input Specification

The first line contains four space-separated integers ~N~, ~A~, ~B~, and ~K~, which represent the number of households, number of telephone lines from Keenan Mobile Phones, number of telephone lines from Chris Home Telephone and the minimum pairs of homes that need to be able to communicate with each other, respectively.

The next ~A~ lines each contain three space-separated integers ~u~, ~v~, and ~l~, which represent a Keenan Mobile Phones telephone line between household ~u~ and ~v~ ~(1 \le u, v \le N)~ that has a level ~l~ ~(1 \le l \le 10^9)~.

The next ~B~ lines have the same format as the previous ~A~ lines but for Chris Home Telephone.

Marks Awarded	Bounds on ~N~	Bounds on ~A~ and ~B~	Bounds on ~K~	Additional Constraints
~6~ marks	~1 \le N \le 2\,000~	~0 \le A, B \le 200\,000~	~0 \le K \le \frac{N(N - 1)}{2}~	None
~5~ marks	~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 only connects to odd indexed households; Chris Home Telephone only connects to even indexed households
~6~ marks	~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}~	None
~8~ marks	~1 \le N \le 200\,000~	~0 \le A, B \le 200\,000~	~0 \le K \le \frac{N(N - 1)}{2}~	None

Output Specification

Output the cheapest cost needed to connect at least ~K~ different pairs of households or -1 if it is not possible.

Sample 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 for Sample Input

33

Explanation of Output for Sample Input

For each company, consider these pictures of the way the ~6~ households are connected by telephone lines:

If Jason buys phone plan level ~3~ from Keenan Mobile Phones and phone plan level ~30~ from Chris Home Telephone, then ~(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)~ can communicate through Keenan Mobile Phones' lines and ~(1, 5), (2, 6), (3, 6), (2, 3)~ can communicate through Chris Home Telephone's lines. There are no cheaper ways.