LCC/Moose '20 Contest 3 S4 - Minimum Maximum Edge

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You are given a connected undirected graph with nodes and edges, where each edge has a weight and a value . In one operation you can decrease the weight of some edge by , edge weights can be zero or negative. You are to perform at most operations, and then choose some connected subgraph of the graph containing all nodes (possibly the graph itself). Of all possible ways of doing so, you want to minimize the maximum edge weight of the connected subgraph.

Input Specification

The first line contains integers , , and .

The next lines contain integers , indicating an undirected edge between and with weight and value . There may be repeated edges.

Output Specification

On one line you are to print the minimum maximum edge weight of the connected subgraph.

No further constraints.

Sample Input

4 4 5
1 2 2 1
2 3 3 2
3 4 4 3
4 1 1 4

Sample Output

-1