Maximize Adjustment Efficiency in a Directed Acyclic Transportation Network

Sichuan Uncle Fang decides to import coconut trees from Hainan to get rich. His modern coconut plantation features a unique transportation network. The network is modeled as a directed acyclic graph with N+2 nodes and M edges. Node N+1 is the entrance (source) and node N+2 is the exit (sink). Each edge is described by six parameters: \(u_i, v_i, a_i, b_i, c_i, d_i\). The edge goes from node \(u_i\) to node \(v_i\). If you compress (reduce) its capacity by 1 unit the cost is \(a_i\); if you expand (increase) the capacity by 1 unit the cost is \(b_i\). The current capacity of the edge is \(c_i\) and each unit of transported goods on that edge costs \(d_i\) to move.

Initially, every edge is fully utilized, which means that the flow on every edge exactly equals its capacity. Moreover, there is exactly one edge connected to the entrance (node \(N+1\)); because damaging that edge would paralyze the whole network, Uncle Fang refuses to adjust it. All the other edges may be adjusted.

There are two types of adjustments:

• Compression: Choose an edge and compress it by 1 unit. Its capacity decreases by 1 unit and you pay \(a_i\).
• Expansion: Choose an edge and expand it by 1 unit. Its capacity increases by 1 unit and you pay \(b_i\).

You can perform adjustments any (integral) number of times on any modifiable edge. After adjustments, the following conditions must hold:

• Every edge remains fully utilized (that is, the flow on it equals its new capacity).
• The overall transportation volume (the total flow from the entrance to the exit) does not decrease. Note that since the unique edge from the entrance is not adjusted and its capacity is \(F\) (say), every edge on the used routes must have capacity at least \(F\) after adjustments.

The total cost of the network is defined as:

[ \text{Total Cost} = \text{Transportation Cost} + \text{Adjustment Cost}, ]

Initially, the cost \(X\) is the sum over all edges of \(c_i\;d_i\) (since there is no adjustment cost). After adjustments, let the new cost be \(Y\) (which includes both the new transportation cost and the total adjustment cost). Uncle Fang must perform at least one adjustment, and he wishes to maximize the adjustment efficiency defined as the average cost saving per adjustment, i.e., maximize

[ \frac{X - Y}{k}, ]

where \(k\) is the total number of adjustments made.

Observations and Restrictions:

• For each modifiable edge, if its original capacity \(c_i\) is greater than \(F\) (the capacity of the fixed edge), you can compress it. Compressing one unit reduces the transportation cost by \(d_i\) but costs \(a_i\). Thus, the net saving per unit is \(d_i - a_i\).
• If \(c_i\) is less than \(F\), you must expand it to \(F\) in order to keep the overall throughput, which incurs an extra cost per unit of \(d_i + b_i\) (i.e. a negative saving of \(-(d_i+b_i)\)).
• If \(c_i = F\), there is no benefit from an adjustment.

Since adjustments are independent and linear in cost for each edge, the optimal strategy is to choose a single modifiable edge and perform a number of adjustments on it. The maximum achievable efficiency is thus the maximum over the modifiable edges of:

• If \(c_i > F\): \(d_i - a_i\)
• If \(c_i < F\): \(- (d_i + b_i)\)

Your task is to compute this maximum adjustment efficiency value. Note that if no adjustment would yield a positive saving, you still must perform an adjustment; in that case, output the maximum (least negative) efficiency.

inputFormat

The first line contains two integers: \(N\) and \(M\) (\(1 \leq N, M \leq 10^5\)). There are a total of \(N+2\) nodes. Node \(N+1\) is the entrance and node \(N+2\) is the exit.

Each of the following \(M\) lines contains six integers: \(u_i\), \(v_i\), \(a_i\), \(b_i\), \(c_i\), and \(d_i\) describing an edge. It is guaranteed that there is exactly one edge for which \(u_i = N+1\) (the fixed edge, which is not allowed to be adjusted).

outputFormat

Output a single integer denoting the maximum possible value of \(\frac{X-Y}{k}\) achievable by some valid adjustment strategy.

sample

3 4
4 2 100 100 10 5
2 3 1 2 15 10
3 5 2 3 10 4
2 5 3 5 8 7

9