## CCO '22 P5 - Phone Plans

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types

The mayor of CCOland, Jason, wants to install telephone lines amongst households, which are numbered from to . 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 , then you are able to use all the telephone lines whose level is less than or equal to that is associated with that company. A phone plan of level costs , and you cannot pick a phone plan of less than .

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 different pairs of households that can communicate with each other.

#### Input Specification

The first line contains four space-separated integers , , , and , 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 lines each contain three space-separated integers , , and , which represent a Keenan Mobile Phones telephone line between household and that has a level .

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

Marks Awarded Bounds on Bounds on and Bounds on Additional Constraints
marks None
marks Keenan Mobile Phones only connects to odd indexed households; Chris Home Telephone only connects to even indexed households
marks ; None
marks None

#### Output Specification

Output the cheapest cost needed to connect at least 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 households are connected by telephone lines:

Keenan Mobile Phones
Chris Home Telephone

If Jason buys phone plan level from Keenan Mobile Phones and phone plan level from Chris Home Telephone, then can communicate through Keenan Mobile Phones' lines and can communicate through Chris Home Telephone's lines. There are no cheaper ways.