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?
The edges form a forest (i.e., an acyclic undirected graph).
The first line contains integers , , and .
The next lines each contain integers , , , and .
Output a single integer, representing the minimum possible unevenness of the resulting forest.
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
For example, one solution is to remove the first, fourth, and sixth edges, giving an unevenness of .