**请注意本题特殊的时限。**
小 X 来到了 Z 市，Z 市有 $n$ 个交通路口，$m$ 条马路。其中第 $i$ 条马路连接着第 $u_i$ 个交通路口和第 $v_i$ 个交通路口（可以从 $u_i$ 到 $v_i$，也可以从 $v_i$ 到 $u_i$），小 X 通过这条马路时要花费 $p_i$ 秒，若有限速，则通过这条马路时要花费 $q_i$ 秒。
现在，市长要在 $k$ 条马路上添加限速，然而，要在哪 $k$ 条马路上限速是小 X 自己规定的。
同时，市长会在每个交通路口处添加红绿灯。第 $i$ 个交通路口的红绿灯先亮绿灯 $x_i$ 秒，再亮黄灯 $y_i$ 秒，之后亮红灯 $z_i$ 秒，然后再亮绿灯，黄灯，红灯，如此往复。如果一个交通路口的红绿灯不是红灯，小 X 可以从这个交通路口出发，到达另一个交通路口。若到达交通路口时，灯的颜色瞬间变了，则按照变了之后的灯计算，灯的黄灯和红灯的持续时间可能为 $0$。并且，小 X 最多只能闯 $g$ 次黄灯。
过了一会儿，市长突然发现，所有的红绿灯在某一刻都变成了绿灯。与此同时，小 X 从第 $1$ 个路口出发，前往第 $n$ 个路口。他想问你，他至少要花多少时间才能到达第 $n$ 个路口？
因为路虽远，行则将至，数据保证一定可以到达，即 $1\sim n$ 一定连通。
## Input
第 $1$ 行 $4$ 个整数 $n,m,k,g$。
接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,z_i$。
接下来 $m$ 行，每行 $4$ 个整数 $u_i,v_i,p_i,q_i$。
## Output
一行，为小 X 花费的最少的时间。
[samples]
## Background
$update$ $on$ $2023.8.17$ $12:25$
**数据修复&加强完成，可重新提交代码。**
路虽远，行则将至。
## Note
**本题采用捆绑测试。**
| Subtask | $n,m$ | $y_i,z_i$ | $k,g$ | 分值 |
| :-: | :-: | :-: | :-: | :-: |
| $0$ | $1 \le n,m \le 5$ | 无特殊限制 | 无特殊限制 | $20$ |
| $1$ | 无特殊限制 | $y_i=z_i=0$ | $k=g=0$ | $5$ |
| $2$ | 无特殊限制 | $y_i=0,0 \le z_i \le 10^9$ | 无特殊限制 | $25$ |
| $3$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | $50$ |
对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$，$0 \le k,g \le m$，$1 \le x_i \le 10^9$，$0 \le y_i,z_i \le 10^9$，$1 \le u,v \le n$，$0 \leq p_i \leq q_i \leq 10^9$。
### 样例解释 #1：
$1 \to 3 \to 4 \to 5$ 并在编号为 $1,2,4,6,7,8$ 的马路上添加限速，到 $3$ 时闯黄灯，到 $4$ 时绿灯直接过，这时候，$1 \to 3$ 花费 $1$ 秒，$3 \to 4$ 花费 $0$ 秒，$4 \to 5$ 花费 $3$ 秒，共花费 $4$ 秒。
### 样例解释 #2：
$1 \to 2 \to 5 \to 6 \to 9$ 并在编号为 $2,3,4,5,6,7,8,9,10,11,13,14,15,16$ 的马路上添加限速，到 $2,5$ 时闯黄灯，到 $4$ 时绿灯直接过，到 $6$ 时等 $1$ 秒红灯，这时候，$1 \to 2$ 花费 $1$ 秒，$2 \to 5$ 花费 $4$ 秒，$5 \to 6$ 花费 $9$ 秒，$6 \to 9$ 花费 $3$ 秒，加上等红灯的 $1$ 秒共花费 $18$ 秒。