U307512 出发

Rab 要去看欧冠决赛了。

Rab 是国家 $1$ 的一名初中生。自然，他看球赛必须乘飞机前往国家 $n$，但不一定有直飞的飞机。每条两国间的飞机航线都有机票价、飞行时间、可出发时段，每个国家都有过路费、经过时间、可进入时段。显然，Rab 没有那么多的钱可以在去看球的路上周游列国，也没有那么多的时间浪费在路途中。所以，他想请你帮助他求出在所有的钱花完前从国家 $1$ 到达国家 $n$ 最少耗费的时间。

第一行三个数 $n,m,k$ 表示有 $n$ 个国家和 $m$ 条航线，Rab 有 $k$ 元钱。 随后 $n$ 行，其中第 $i$ 行四个数 $a_i,b_i,c_i,d_i$ 表示经过第 $i$ 个国家需支付 $a_i$ 元过路费，消耗 $b_i$ 时间，且该国只可在 $c_i \sim d_i$ 时间段内进入。 随后 $m$ 行，其中第 $i$ 行六个数 $u_i,v_i,x_i,y_i,s_i,t_i$ 表示第 $u_i$ 个国家到第 $v_i$ 个国家之间有一条机票价为 $x_i$、飞行时间为 $y_i$ 的双向航线，这条航线可以在 $s_i \sim t_i$ 时间段内出发。

一行一个数表示在 $k$ 元钱花完前从国家 $1$ 到达国家 $n$ 最少耗费的时间，若无法在 $k$ 元钱花完前从国家 $1$ 到达国家 $n$ 输出 $-1$。

请注意每个国家**没有**可离开时段限制，每条航线也**没有**可到达时段限制。