约翰农场的牛奶输送网络由 M 条管道（1\le M\le 500）组成，这些管道用于将牛奶从牛棚输送到牛奶储存罐。他计划在未来一年内移除并更新大部分管道，但希望保留一条完整的管道路径，以便仍能将牛奶从牛棚输送到储存罐。

该管道网络由 N 个连接点（1\le N\le 500）描述，每个连接点可以作为一组管道的端点。连接点 1 是牛棚，连接点 N 是储存罐。每条双向管道连接一对连接点，并具有相关的延迟（牛奶从管道一端到达另一端所需的时间）和容量（在稳定状态下每单位时间可以通过管道输送的牛奶量）。同一对连接点之间可以有多条管道连接。

对于从牛棚到储存罐的管道路径，路径的延迟是路径上各管道延迟的总和，路径的容量是路径上各管道容量的最小值（因为这是限制牛奶通过路径的整体速率的「瓶颈」）。如果约翰想通过一条延迟为 L、容量为 C 的管道路径输送总量为 X 的牛奶，则所需时间为 L + X\div C。

给定约翰的管道网络结构，请帮助他选择一条从牛棚到储存罐的路径，使他能够在最短的总时间内输送 X 单位的牛奶。

第 1 行：\ 三个用空格分隔的整数：N M X (1\le X\le 10^6)。

第 2 行到第 M+1 行：\ 每行描述一条管道，包含 4 个整数：I J L C。\ I 和 J (1\le I, J\le N) 是管道连接的两个连接点。\ L 和 C (1\le L, C\le 10^6) 分别是管道的延迟和容量。

仅有一行、一个整数：\ 约翰沿着一条路径送牛奶所花费的最少时间（向下取整到最近的整数）。

约翰想通过他的管道网络输送 15 单位的牛奶。管道 1 连接连接点 1（牛棚）和连接点 2，延迟为 10，容量为 3。管道 2 和 3 也以类似的方式定义。

路径 1\to3 需要 14 + 15\div1 = 29 单位的时间。路径 1\to 2\to 3 需要 20 + 15\div2 = 27.5 单位的时间，因此是最优的。

USACO