Uncle Fang's Coconut Transport

Uncle Fang from Sichuan, in order to get rich, decided to introduce coconut trees from Hainan. Uncle Fang's coconut garden is very modern and features a unique transportation system.

We use points to represent traffic nodes and edges to represent roads. Thus, Uncle Fang's coconut garden can be viewed as a directed acyclic graph with $n + 2$ traffic nodes and $m$ edges. Node $n + 1$ is the entrance, and node $n + 2$ is the exit. Each road has 6 parameters: $u_i, v_i, a_i, b_i, c_i, d_i$, which represent that the road goes from node $u_i$ to node $v_i$, the cost to compress its capacity by one unit is $a_i$, the cost to expand its capacity by one unit is $b_i$, the current upper limit of the road's transport capacity is $c_i$, and the cost per unit of transport through this road is $d_i$.

In this traffic network, only one road is connected to the starting point. Because damaging this road would paralyze the entire traffic network, the clever Uncle Fang has decided never to adjust this road. That is to say, except for this road, all other roads can be adjusted.

There are two types of adjustments: 1. Select a road and compress it once; the capacity of this road decreases by 1 unit. 2. Select a road and expand it once; the capacity of this road increases by 1 unit.

A road can be adjusted multiple times.

Because Uncle Fang hired an engineer a long time ago to perform a major optimization on this traffic network, all roads are currently fully utilized, meaning the load of every road is full (the flow of each road equals its capacity).

However, when Uncle Fang thinks about the bumper harvest of his Hainan coconuts, he is very worried that the huge transport volume will lead to excessive costs. Therefore, Uncle Fang decided to perform at least one adjustment. After the adjustment, it is mandatory to keep every road fully loaded, and the total traffic volume must not decrease.

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

Note: Total cost = transport cost of the traffic network + cost of adjustments.

Input

The first line contains two integers $n, m$. The next $m$ lines represent $m$ edges, describing the traffic network. Each line contains 6 integers representing $u_i, v_i, a_i, b_i, c_i, d_i$. The next 1 line contains 1 edge, representing the edge connected to the starting point.

Output

A floating-point number, rounded to 2 decimal places, representing the required answer. The data guarantees the answer is greater than 0.

Examples

Input 1

6 7
1 2 0 0 1 1000
2 4 0 0 1 1000
4 6 0 0 1 1000
1 3 0 0 0 0
3 5 0 0 0 0
5 6 0 0 0 0
6 8 0 0 1 0
7 1 0 0 1 0

Output 1

500.00

Constraints

For 20% of the data, $1 \le n \le 5, 0 \le m \le 10$. For 40% of the data, $1 \le n \le 50, 0 \le m \le 300$. For 100% of the data, $1 \le n \le 500, 0 \le m \le 3000, 1 \le u_i, v_i \le n + 2$, $0 \le a_i, b_i \le 50, 0 \le c_i \le 1000, 0 \le d_i \le 1000$.