問題文

$N$ 頂点 $K$ 辺の連結な単純無向グラフ $G = (V, E)$ があります。
それぞれの頂点には $1$ から $N$ までの番号が、辺には $1$ から $K$ までの番号がついていて、 $i$ 番の辺は番号が $u_i$ と $v_i$ の頂点を結んでおり、コスト $w_i$ と利益 $p_i$ が定まっています。
$G$ の全域木 $T$ に対して、その辺の番号の集合を $I$ として、次のように $T$ のコスト $W(T)$ と利益 $P(T)$ を定義します。

• $\displaystyle W(T) = \sum_{i \in I} w_i$
• $\displaystyle P(T) = \max_{i \in I}\ p_i$

入力

$N \ K \ C$
$u_1 \ v_1 \ w_1 \ p_1$
$u_2 \ v_2 \ w_2 \ p_2$
$\vdots$
$u_K \ v_K \ w_K \ p_K$

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• $1 \leq C \leq 10^{10}$
• $1 \leq w_i, p_i \leq 10^{5}$ $(i = 1, 2, \cdots, K)$
• 与えられるグラフは連結な単純無向グラフ
• 入力はすべて整数

出力

条件を満たす $T$ について、$P(T)$ の最大値を出力してください。 条件を満たす $T$ が存在しない場合は $-1$ を出力してください。

サンプル

3 3 1000
1 2 20 20
2 3 10 10
3 1 1 1

20    

5 7 10
1 2 3 4
1 3 2 4
2 3 10 20
3 4 1 3
2 4 2 2
2 5 4 2
4 5 3 3

4  

3 3 1
1 2 100 100
2 3 100 100
3 1 100 100

-1