Milk Routing

Interview

Time limit1sMemory limit128 MB

Summary

Pick a single path from node 1 to node N minimizing latency plus X divided by the path's bottleneck capacity, and floor the result.

Level: Medium5 of 10
Topics: Graph, Shortest path, Binary search, Greedy
Solved: No attempts yet

Problem

Farmer John's farm has an outdated network of $M$ pipes ( $1 \le M \le 500$ ) for pumping milk from the barn to his milk storage tank. He wants to remove and replace most of them over the next year, but he wants to leave exactly one path worth of pipes intact so that he can still pump milk from the barn to the storage tank.

The pipe network consists of $N$ junction points ( $1 \le N \le 500$ ), each of which can serve as an endpoint for a set of pipes. Junction point $1$ is the barn, and junction point $N$ is the storage tank. Each of the $M$ pipes is bidirectional, runs between a pair of junction points, and has an associated latency (the time it takes milk to travel from one end of the pipe to the other) and capacity (the amount of milk per unit time that can be pumped through it in steady state). Multiple pipes may connect the same pair of junction points.

For a path of pipes from the barn to the tank, the latency of the path is the sum of the latencies of its pipes, and the capacity of the path is the minimum of the capacities of its pipes (this minimum is the bottleneck that constrains the overall pumping rate). Sending $X$ units of milk through a path with latency $L$ and capacity $C$ takes $L + X/C$ time.

Given the pipe network, choose a single path from the barn to the storage tank that lets Farmer John pump $X$ units of milk in the minimum total time, and report that minimum time.

Input

Line 1: Three space-separated integers $N$ , $M$ , and $X$ ( $1 \le X \le 1{,}000{,}000$ ).
Lines 2 through $M+1$ : Each line describes one pipe with four integers $I$ , $J$ , $L$ , $C$ . $I$ and $J$ ( $1 \le I, J \le N$ ) are the junction points at the two ends of the pipe, and $L$ and $C$ ( $1 \le L, C \le 1{,}000{,}000$ ) are its latency and capacity.

Output

Line 1: The minimum time needed to send the milk along a single path, rounded down to the nearest integer.

Hint

Suppose $X = 15$ units of milk must be sent. Using only the pipe that directly connects junction point $1$ (the barn) to junction point $3$ (the tank), with latency $14$ and capacity $1$ , takes $14 + 15/1 = 29$ . The path $1 \to 2 \to 3$ instead has latency $10 + 10 = 20$ and capacity $\min(3, 2) = 2$ , taking $20 + 15/2 = 27.5$ , which is better. Rounded down, the answer is $27$ .

Examples3

Example 1
Input
```
3 3 15
1 2 10 3
3 2 10 2
1 3 14 1
```
Expected output
```
27
```
Example 2
Input
```
2 1 100
1 2 5 10
```
Expected output
```
15
```
Example 3
Input
```
2 2 10
1 2 1 1
1 2 5 5
```
Expected output
```
7
```