## DMOPC '21 Contest 1 P4 - Uneven Forest

View as PDF

Points: 20
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type

As a realist hero, you know that forests should be as even as possible, or some trees may grow too large and hog all of the sunlight. Specifically, the unevenness of a forest is the length of the longest simple path in that forest. The forest you are to manage consists of nodes and edges, where the -th edge connects nodes and with a length of and a beauty of . You may remove some set of edges in the forest with your magical saw, but the sum of the beauty of the edges removed must not exceed . Given these conditions, what is the minimum possible unevenness of the resulting forest?

#### Constraints

The edges form a forest (i.e., an acyclic undirected graph).

#### Input Specification

The first line contains integers , , and .

The next lines each contain integers , , , and .

#### Output Specification

Output a single integer, representing the minimum possible unevenness of the resulting forest.

#### Sample Input

10 7 6
1 3 2 1
3 2 1 3
3 4 2 5
5 4 3 2
7 6 2 4
4 6 4 3
9 10 3 2

#### Sample Output

3

#### Explanation

For example, one solution is to remove the first, fourth, and sixth edges, giving an unevenness of .