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?

Constraints

~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).

Input Specification

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 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 ~3~.