Description

To get rich, Uncle Fang from Sichuan decides to introduce coconut trees from Hainan. His coconut plantation is highly modernized, with a unique transportation system inside.

We model transportation junctions as nodes and roads as edges. Thus, the plantation can be seen as a directed acyclic graph (DAG) with $N + 2$ transportation nodes and $M$ edges. Node $N + 1$ is the entrance (source), and node $N + 2$ is the exit (sink). Each road has six parameters $u_i, v_i, a_i, b_i, c_i, d_i$, meaning the road goes from node $u_i$ to node $v_i$; compressing its capacity by $1$ unit costs $a_i$; expanding its capacity by $1$ unit costs $b_i$; its current capacity upper bound is $c_i$; and transporting each unit of flow along this road costs $d_i$.

In this transportation network, there is exactly one edge outgoing from the source. Since damaging this road would paralyze the entire network, the clever Uncle Fang decides never to adjust this road. That is, all other roads can be adjusted.

There are two types of adjustments:

• Choose a road and compress it once; the capacity of this road decreases by $1$ unit.
• Choose a road and expand it once; the capacity of this road increases by $1$ unit.

A road can be adjusted multiple times.

A long time ago, Uncle Fang hired an engineer to optimize this transportation network. So now every road is fully utilized, i.e., the load on each road is at its limit (the flow on each road equals its capacity).

However, thinking of the upcoming bumper harvest of Hainan coconuts, Uncle Fang worries that the huge transportation volume will cause excessive costs. Therefore, he decides to perform at least one adjustment. After the adjustments, every road must remain fully utilized, and the total throughput must not decrease.

Let the total cost after adjustments be $Y$, and the total cost before adjustments be $X$. Uncle Fang wants to know the optimal adjustment ratio, i.e., if he performs $k$ adjustments in total, what is the maximum possible value of $\dfrac{X - Y}{k}$?

Note: total cost $=$ transportation cost $+$ adjustment cost.

Input Format

The first line contains two integers $N, M$. The next $M$ lines describe the $M$ edges of the transportation network. Each line contains six integers $u_i, v_i, a_i, b_i, c_i, d_i$.

Output Format

Output a floating-point number with two decimal places, representing the answer. The testdata guarantees the answer is greater than $0$.

5 10
1 5 13 13 0 412
2 5 30 18 396 148
1 5 33 31 0 39
4 5 22 4 0 786
4 5 13 32 0 561
4 5 3 48 0 460
2 5 32 47 604 258
5 7 44 37 75 164
5 7 34 50 925 441
6 2 26 38 1000 22

103.00

Hint

Constraints: For all testdata, $1 \le N \le 5 \times 10^3$, $1 \le M \le 3 \times 10^3$, $1 \le u_i, v_i \le N + 2$, $0 \le a_i, b_i \le 500$, $0 \le c_i \le 10^4$, $0 \le d_i \le 10^3$.

Translated by ChatGPT 5