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 ~N~ nodes and ~M~ edges, where the ~i~-th edge connects nodes ~u_i~ and ~v_i~ with a length of ~l_i~ and a beauty of ~b_i~. 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 ~K~. Given these conditions, what is the minimum possible unevenness of the resulting forest?
~1 \le M < N \le 10^3~
~1 \le u_i, v_i \le N~
~1 \le l_i, b_i, K \le 10^9~
The edges form a forest (i.e., an acyclic undirected graph).
The first line contains ~3~ integers ~N~, ~M~, and ~K~.
The next ~M~ lines each contain ~4~ integers ~u_i~, ~v_i~, ~l_i~, and ~b_i~.
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 ~3~.