Start of the new journey#9554
The day came, ladies and gentlemen! We are taking the bride! However, as always, we are left with narrow roads of Baku and kids block the way of the cars and want some money traditionally. Poor Rashad doesn't have much money to spend on kids! Also, he wants as many cars as possible going alongside him. He thought a lot and decided to choose a path with maximum effectiveness. The effectiveness of the path is defined by the maximum number of cars he can take divided by the total cost he needs to give to children (effectiveness = number_of_cars / total_cost). When starting a path, the number of cars Rashad can take is equal to the minimum width of all roads in the path. We are given the available roads of Baku, with each road having its width and cost and connecting two locations, and you need to find the maximum effectiveness of the possible path going from location to location . See the output format for output details.
The numbers (1 \le N \le 10^3) and (1 \le M \le 10^4) are given in the first line. Each of next lines contain numbers, the first endpoint of the road, the second endpoint of the road, the cost of the road x_i (1 \le x_i \le 10^3), and the width of the road y_i (1 \le y_i \le 10^3).
Print times the maximum effectiveness of the road, rounded down to the nearest integer.
Example 1
In this example, there is only one path from to . The width is \min(3, 4) = 3 and the cost is 2 + 5 = 7. 3/7 = 0.428571428571..