Minimizing Total Mission Risk

A secret military base of country K is built underground for security purposes. The base has two rows of large skylight entrances (i.e. entry/exit points) on the surface. There are n₁ entrances in total. One row contains the odd‐numbered entrances (1, 3, 5, …) and the other contains the even‐numbered entrances (2, 4, 6, …), where the largest label is n₁.

Inside the base, there are many isolated chambers. Each chamber is connected to exactly two entrances – one from the odd row and one from the even row. A chamber can be explored if at least one of its two entrances is reached by a special forces team.

You are given a map of n checkpoints and m one‐way roads, where checkpoints 1 through n₁ represent the base entrances, and checkpoint n is your own starting base. Each road from point u to point v is described by its travel time t and its safety coefficient s. Note that only one–way roads exist and the map contains no cycles.

A special forces team is dispatched from your base (node n) to an entrance. Once a team is dropped at an entrance, only the chambers directly connected to that entrance are explored. You have enough teams at your disposal, but you wish to minimize the total mission risk. The risk associated with a team that travels along a path is defined as the ratio:

[ \text{Risk} = \frac{\text{(sum of travel times)}}{\text{(sum of safety coefficients)}} ]

The overall mission risk is the sum of the risks of all teams deployed. Since every chamber (which connects one odd entrance and one even entrance) must be explored, the set of entrances where you dispatch teams must form a vertex cover for the complete bipartite graph formed by the odd and even entrances. It can be shown that any vertex cover of such a graph, in order to cover every chamber, must be either all odd entrances or all even entrances.

Your task is to determine, for each entrance v (1 ≤ v ≤ n₁), the minimum achievable risk along any path from your base (node n) to that entrance. Then, compute the sum of these risk values for the odd entrances and for the even entrances separately, and output the smaller of these two sums. In other words, if A is the set of odd entrances and B is the set of even entrances, the answer is

[ \min\Biggl{ \sum_{v \in A} r_v,; \sum_{v \in B} r_v \Biggr} ]

Note on computing the minimum risk per entrance: The risk of a path is defined as \(\frac{T}{S}\) where \(T\) is the sum of travel times and \(S\) is the sum of safety coefficients along that path. Since the graph is a directed acyclic graph (DAG), one can use binary search in combination with dynamic programming along a topologically sorted order to determine, for each entrance, the minimal value \(r_v\) satisfying the condition that there exists a path from node n to v with \(\frac{T}{S} \le r_v\).

Help complete this mission before the enemy declares you one of their own!

inputFormat

The first line contains three integers n, m, and n₁ (the number of checkpoints, the number of roads, and the number of entrances respectively).

Each of the next m lines contains four integers: u, v, t, and s, indicating there is a one-way road from checkpoint u to checkpoint v with travel time t and safety coefficient s.

It is guaranteed that the road network is a DAG. Checkpoints 1 through n₁ are the entrances of the enemy base, and checkpoint n is your base.

outputFormat

Output a single real number: the minimum total mission risk (i.e. the minimum between the sum of risks for all odd entrances and the sum of risks for all even entrances). Print the answer with at least 6 decimal places of precision.

sample

5 5 2
5 3 10 2
3 1 5 1
5 4 2 1
4 2 8 4
3 4 1 1

2.000000

</p>