Earthquake Recovery

There is a graph with N vertices and M undirected edges. An earthquake has destroyed every edge, and you want to restore some of the given edges so that every vertex can reach every other vertex. In other words, the restored edges must connect all vertices.

A reference amount F is given. Each edge has a restoration cost c and a restoration time t. The same pair of vertices may appear multiple times, with different costs or times. The input always guarantees that the vertices can be connected somehow, even if the total restoration cost is greater than F.

Let C be the total cost of the restored edges and T be their total time. The gain is F - C, and the gain per unit time is (F - C) / T. Find the maximum possible gain per unit time.

The first line contains three integers N, M, and F.

Each of the next M lines contains edge information i j c t. The edge connects vertices i and j, has restoration cost c, and has restoration time t.

The constraints are:

• 4 <= N <= 400
• 1 <= M <= 10,000
• 1 <= F <= 2,000,000,000
• 1 <= c, t <= 2,000,000,000

Print the maximum gain per unit time, rounded to four digits after the decimal point. If the maximum gain is not positive, print 0.0000.

For the public test, restoring the 2nd, 3rd, 4th, and 5th listed edges is optimal. Their total cost is 83 and their total time is 16, so the gain is 100 - 83 = 17, and the gain per unit time is 17 / 16 = 1.0625.