题目描述

农民约翰的农场有一套老旧的管网，管网由$\red{M}$条管道$\red{(1<=M<=500)}$构成，用于将牛奶从谷仓运到储奶罐。 他想在明年移除和更新大部分管道，但他想原封不动地保留一条完整的路径，这样他仍然可以把牛奶从谷仓输送到储罐。

管网由$\red{N}$个节点$\red{(1<=N<=500)}$组成，每个点都可以作为一组管道的端点。结点$\red{1}$是谷仓，结点$\red{N}$是储罐。$\red{M}$条双向管道中的每一条都连接一对节点，并且都有一个延迟值$\red{(}$牛奶达到管的另一端的用时$\red{)}$和容量值$\red{(}$单位时间内可以稳定通过管道的牛奶量$\red{)}$。多条管道可以连接同一对节点。

对于一条连接谷仓与储罐的路径，路径的延迟等于沿途所有管道的延迟之和，路径的容量等于沿途管道最小的容量$\red{(}$因为这是制约牛奶运送的"瓶颈"$\red{)}$。如果约翰通过一条延迟为$\red{L}$、容量为$\red{C}$的管道运送$\red{X}$个单位的牛奶，需要的时间为$\red{L+X/C}$。

给出约翰的管网结构，请帮助他选择一条路径，使得他从谷仓到储罐运送$\red{X}$个单位牛奶的总时间最少。

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

27

提示

$\red{FJ }$想通过他的管网发送 $\red{15 }$个单位的牛奶。管道 #$\red{1 }$将连接点 $\red{1（}$谷仓）连接到连接点 $\red{2，}$延迟为 $\red{10，}$容量为 $\red{3}$。管道 #$\red{2 }$和 #$\red{3 }$ 的定义类似。

路径 $\red{1->3 }$需要 $\red{14 + 15/1 = 29 }$个时间单位。路径 $\red{1->2->3 }$需要 $\red{20 + 15/2 = 27.5 }$个时间单位，因此是最优的。

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

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