P10054 [CCO 2022] Phone Plans

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.

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

## 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}$. Subtask ID|Score|$N$|$A, B$|Additional Constraints :-:|:-:|:-:|:-:|:-: $1$|$24$|$1 \leq N \leq 2000$|$0 \leq A, B \leq 2\times 10^5$|None. $2$|$20$|$1 \leq N \leq 2\times 10^5$|$1 \leq N \leq 2\times 10^5$|Keenan Mobile only connects households with odd indices; Chris Home Phone only connects households with even indices. $3$|$24$|$1 \leq N \leq 2\times 10^5$|$0 \leq A \leq 10$|None. $4$|$32$|$1 \leq N \leq 2\times 10^5$|$0 \leq A, B \leq 2\times 10^5$|None. # Input Format # Output Format # Hint Translated by ChatGPT 5