巴伊托恰（Bajtocja）拥有世界上最大的褐煤矿。每天，煤炭都会通过铁路网运输到巴伊托恰的所有城市，以便居民取暖。
运输过程如下：首先，一定数量的火车从矿山所在的城市出发，前往其他几个城市；然后，从这些城市再有火车开往其他城市，以此类推。对于巴伊托恰的每个城市，至少存在一个火车序列 $p_{1}, p_{2}, \ldots, p_{k}$，使得煤炭从矿山装载到火车 $p_{1}$，然后依次将煤炭从火车 $p_{i}$ 转载到火车 $p_{i+1}$（对于 $i = 1, \ldots, k - 1$），直到最终煤炭通过火车 $p_{k}$ 运达该城市。每个城市（除了矿山所在的城市）可能会有几列火车到达，但不会出现循环——如果你在一个城市乘坐火车，你肯定不会通过铁路回到那个城市。
火车之间是连通的——发车时间经过精心安排，只有在所有计划运送矿山煤炭的火车都到达某个城市后，火车才会从该城市出发。如果一列火车晚点，也可能导致其他火车晚点。铁路工人计划罢工：他们可以使一列火车停运恰好 $k$ 分钟。他们打算选择一列火车，以使所有火车的总延误时间最大化。
输入格式
输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 400$, $1 \le m \le 80\,000$），分别表示巴伊托恰的城市数量和直达铁路连接数量。下一行包含一个整数 $k$（$1 \le k \le 10^{9}$），表示铁路工人使火车停运的最大延误时间。城市编号从1到 $n$；矿山位于编号为1的城市。
接下来的 $m$ 行，每行包含四个整数 $a_{i}$、$b_{i}$、$w_{i}$、$p_{i}$（$1 \le a_{i}, b_{i} \le n$, $0 \le w_{i}, p_{i} \le 10^{9}$, $0 \le w_{i} + p_{i} \le 10^{9}$）。它们表示根据时刻表，第 $i$ 列火车在日出后 $w_{i}$ 分钟准时从城市 $a_{i}$ 出发，并在 $p_{i}$ 分钟后准时到达城市 $b_{i}$，都是在同一天（巴伊托恰的一天有 $10^{9} + 1$ 分钟）。从城市 $m$ 出发的火车发车时间不小于到达城市 $m$ 的最晚时间。
输出格式
标准输出的第一行也是唯一一行应该包含一个整数——铁路工人罢工可能导致的最大火车总延误时间。
示例
输入
5 5 3 1 2 3 1 1 3 0 3 3 2 4 1 3 4 3 5 2 5 8 2
输出
8