题目描述

在《西游记》中，唐僧师徒一行面临了穿越险恶的妖怪山脉，他们必须选择一条最短时间的路径来前往目的地。山脉由N个关键点组成，每个点都可以被视为路径的一部分。开始点是灵山寺，目的地是西天取经的终点。山脉中有M条双向路径，每一条都连接两个节点，并且有不同的延迟值（穿越该路径所需的时间）和容量值（每单位时间内能通过该路径的经书数量）。多条路径可以连接相同的节点。
对于连接灵山寺和取经终点的路径，路径的延迟是该路径上所有段的延迟之和，路径的容量是该路径上所有段中最小的容量（因为这是经书运输的“瓶颈”）。如果唐僧一行通过一条延迟为L、容量为C的路径运输X本经书，所需的总时间是L + X / C。
现在，请帮助唐僧师徒选择一条路径，以使他们在最短的时间内将X本经书从灵山寺运送到取经终点。您需要根据给定的路径结构和属性，计算出所需的最短时间。

输入格式

第一行包含三个整数N、M和X，分别表示山脉中的节点数、路径数和需要运送的经书数量。1 <= M，N <= 500，1 <= X <= 1,000,000。
接下来M行，每一行描述一条路径，有4个整数：I J L C。I和J(1<=I,J<=N)是这条路径连接的两个点。L和C(1<=L，C<=1000000)是这条路径的延迟和容量。

输出格式

输出一个整数，表示将X本经书从灵山寺运送到取经终点所需的最短时间（向下取整）。

样例

input

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

output

27

提示

想要运送15本经书。路径1连接节点1和节点2，延迟为10，容量为3。路径2和路径3也以相似的方式来定义。
路径1->3花费14+15/1=29个单位的时间。路径1->2->3花费20+15/2=27.5个单位的时间，用时最少。