题目描述

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

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

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

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

输入格式

第${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)}$是这条管道的延迟和容量。

输出格式

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

样例

输入样例

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

输出样例

27

提示

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

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

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

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