Maximizing Profit Per Unit Time in Road Construction

John has rebuilt his n farmlands after a devastating earthquake, and now he wants to connect them by constructing roads. There are m candidate roads available. Each road has a construction time and a building cost. John has agreed to pay f yuan overall once the roads are built that connect all farmlands; however, the cows’ engineering team, who repair the roads, are only interested in maximizing their profit rate, i.e. the ratio of total profit to total construction time.

If a set of roads (forming a spanning tree) has a total construction time of \(T\) and a total building cost of \(S\), then the profit is \(f - S\) and the profit per unit time is given by \( \frac{f - S}{T}\). Note that sometimes \(S>f\) and the profit rate can be negative.

Your task is to help the cows choose which roads to repair so that the profit per unit time is maximized.

Note: It is guaranteed that the farmlands can be connected by some subset of roads.

inputFormat

The first line contains three integers \(n\), \(m\), and \(f\) \( (1 \leq n \leq 10^5,\ 1 \leq m \leq 10^5,\ 1 \leq f \leq 10^9)\) — the number of farmlands, the number of available roads, and the payment John must pay, respectively.

Each of the next \(m\) lines contains four integers \(u\), \(v\), \(t\), and \(c\) \( (1 \leq u,v \leq n,\ 1 \leq t, c \leq 10^9)\), which represent that there is a road connecting farmland \(u\) and farmland \(v\) with construction time \(t\) and building cost \(c\). There can be multiple roads connecting the same pair of farmlands.

outputFormat

Output a single real number which is the maximum profit per unit time that can be achieved. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3 10
1 2 1 3
2 3 2 3
1 3 4 1

1.333333