Project Order Optimization

You are given a collection of projects each with an associated importance score and a list of dependencies between these projects. A dependency (u, v) means that project u must be completed before project v. Your task is to determine if there exists a valid order to complete all projects (i.e. a topological ordering). If such an ordering exists, you need to choose the first k projects after sorting all projects in descending order of their importance scores, so that the sum \(\sum_{i=1}^{k} s_i\) is maximized. If the projects cannot be completed due to cyclic dependencies, output -1.

Note: The output order is determined solely by sorting the projects by their importance scores in descending order, after verifying that the dependency constraints allow for a complete ordering.

Input and output must be handled via standard input (stdin) and standard output (stdout).

inputFormat

The input begins with a line containing three integers n, m, and k, where:

• n is the number of projects,
• m is the number of dependency relations, and
• k is the number of projects to select.

This is followed by n lines, each containing a project identifier (a string) and an importance score (an integer). The next m lines each contain two project identifiers u and v, indicating that project u must be completed before project v.

outputFormat

If a valid project ordering exists (i.e. there is no cycle), output the identifiers of the first k projects obtained by sorting all projects in descending order of their importance scores, separated by a single space. If there is a cycle making the ordering impossible, output -1.

## sample

5 4 3
proj1 5
proj2 10
proj3 8
proj4 6
proj5 7
proj1 proj2
proj2 proj3
proj4 proj2
proj4 proj5

proj2 proj3 proj5

</p>