题目描述

Farmer John's farm has an outdated network of M pipes (1 <= M <= 500) for pumping milk from the barn to his milk storage tank. He wants to remove and update most of these 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 is described by N junction points (1 <= N <= 500), each of which can serve as the endpoint of a set of pipes. Junction point 1 is the barn, and junction point N is the storage tank. Each of the M bi-directional pipes runs between a pair of junction points, and has an associated latency (the amount of time it takes milk to reach one end of the pipe from the other) and capacity (the amount of milk per unit time that can be pumped through the pipe in steady state). Multiple pipes can connect between the same pair of junction points.

For a path of pipes connecting from the barn to the tank, the latency of the path is the sum of the latencies of the pipes along the path, and the capacity of the path is the minimum of the capacities of the pipes along the path (since this is the "bottleneck" constraining the overall rate at which milk can be pumped through the path). If FJ wants to send a total of X units of milk through a path of pipes with latency L and capacity C, the time this takes is therefore L + X/C.

Given the structure of FJ's pipe network, please help him select a single path from the barn to the storage tank that will allow him to pump X units of milk in a minimum amount of total time.

输入格式

* Line 1: Three space-separated integers: N M X (1 <= X <= 1,000,000).

* Lines 2..1+M: Each line describes a pipe using 4 integers: I J L C. I and J (1 <= I,J <= N) are the junction points at both ends of the pipe. L and C (1 <= L,C <= 1,000,000) give the latency and capacity of the pipe.

第1行：三个空格分隔的整数:N M X(1<=X<=1000000)。

第2行到第M+1行：每一行描述一条管道，有4个整数：I J L C。I和J(1<=I,J<=N)是这条管道连接的两个点。L和C(1<=L，C<=1000000)是这条管道的延迟和容量。

输出格式

* Line 1: The minimum amount of time it will take FJ to send milk along a single path, rounded down to the nearest integer.

第1行:约翰沿着一条路径送牛奶花费的最少的时间，向下取整到最近的整数。

3 3 15 
1 2 10 3 
3 2 10 2 
1 3 14 1 

27 

提示

FJ wants to send 15 units of milk through his pipe network. Pipe #1 connects junction point 1 (the barn) to junction point 2, and has a latency of 10 and a capacity of 3. Pipes #2 and #3 are similarly defined.

The path 1->3 takes 14 + 15/1 = 29 units of time. The path 1->2->3 takes 20 + 15/2 = 27.5 units of time, and is therefore optimal.

约翰想要通过管网运送15个单位的牛奶。管道1连接节点1（谷仓）和节点2，延迟为10，容量为3。管道2和管道3也以相似的方式来定义。

路径1->3花费14+15/1=29个单位的时间。路径1->2->3花费20+15/2=27.5个单位的时间，用时最少。