Maximum Scenic Ratio Cycle

In Tibet, a travel entrepreneur X has established a large tourism company with several scenic spots. To improve the travel experience, he designs a set of rail lines connecting the scenic spots. Each rail line is associated with two values: \(V_i\) (the scenic value) and \(P_i\) (the ticket price). When a tourist rides the train, they follow a cycle (i.e. a closed route) without repeating any rail line.

The goal is to find a cycle such that the ratio

[ R = \frac{\sum V_i}{\sum P_i} ]

is maximized among all cycles that can be formed, starting from any scenic spot. Note that the cycle may not necessarily include all scenic spots. If no cycle exists, output 0.

inputFormat

The first line of input contains two integers \(n\) and \(m\) where \(n\) (\(1 \le n \le 100\)) is the number of scenic spots (nodes) and \(m\) (\(1 \le m \le 1000\)) is the number of rail lines (directed edges).

Each of the next \(m\) lines contains four integers \(u\), \(v\), \(V\) and \(P\) representing a directed rail line from spot \(u\) to spot \(v\) with scenic value \(V\) and price \(P\). It is guaranteed that \(P > 0\).

outputFormat

Output a single number which is the maximum ratio \(R = \frac{\sum V_i}{\sum P_i}\) among all cycles in the graph. The answer is considered correct if its absolute error does not exceed \(10^{-6}\). If there is no cycle in the graph, output 0.

sample

3 3
1 2 10 5
2 3 10 5
3 1 10 5

2.000000