Background

$update$ $on$ $2023.8.17$ $12:25$. Testdata has been fixed and strengthened; you can resubmit your code.

The road is long, but if you keep going, you will arrive.

Problem Description

Please note the special time limit of this problem.

Little X arrives in City Z. City Z has $n$ intersections and $m$ roads. The $i$-th road connects intersection $u_i$ and intersection $v_i$ (you can travel from $u_i$ to $v_i$ and also from $v_i$ to $u_i$). Little X needs $p_i$ seconds to pass this road; if there is a speed limit, then passing this road takes $q_i$ seconds.

Now, the mayor will add speed limits to $k$ roads. However, which $k$ roads will have speed limits is decided by Little X.

At the same time, the mayor will install traffic lights at every intersection. The traffic light at intersection $i$ shows green for $x_i$ seconds first, then yellow for $y_i$ seconds, then red for $z_i$ seconds, and then repeats green, yellow, red, and so on. If the traffic light at an intersection is not red, Little X can depart from this intersection to another intersection. If the light color changes at the exact moment he arrives at an intersection, the color after the change is used. The durations of yellow and red may be $0$. Also, Little X can run a yellow light at most $g$ times.

After a while, the mayor suddenly finds that at some moment, all traffic lights turn green. At the same time, Little X starts from intersection $1$ and heads to intersection $n$. He wants to know the minimum time needed to reach intersection $n$.

Because the road is long, but if you keep going, you will arrive. The testdata guarantees that reaching is always possible, i.e., intersections $1 \sim n$ are connected.

Input Format

The first line contains $4$ integers $n,m,k,g$.

The next $n$ lines each contain $3$ integers $x_i,y_i,z_i$.

The next $m$ lines each contain $4$ integers $u_i,v_i,p_i,q_i$.

Output Format

One line: the minimum time Little X needs.

5 8 6 1
1 2 2
1 0 3
1 1 4
3 1 0
5 1 4
1 2 1 4
2 4 2 4
3 4 0 2
1 5 7 8
1 3 1 2
5 4 2 3
2 5 2 4
1 4 4 7

4

9 16 14 2
1 7 2
1 5 3
1 6 4
3 5 0
1 6 5
1 0 4
1 7 5
3 8 8
3 8 6
1 2 1 4
8 5 2 6
2 4 2 4
8 6 3 5
3 4 0 2
6 7 1 4
1 5 7 8
5 9 16 21
1 3 2 2
7 6 2 3
5 4 2 3
6 9 3 5
2 5 2 4
8 9 4 7
1 4 4 7
6 5 6 9

18

Hint

This problem uses bundled tests.

For $100\%$ of the data, it is guaranteed that $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$.

Sample Explanation #1:

Take the path $1 \to 3 \to 4 \to 5$, and add speed limits on the roads with indices $1,2,4,6,7,8$. Run the yellow light when arriving at $3$, and pass directly on green when arriving at $4$. Then $1 \to 3$ takes $1$ second, $3 \to 4$ takes $0$ seconds, $4 \to 5$ takes $3$ seconds, for a total of $4$ seconds.

Sample Explanation #2:

Take the path $1 \to 2 \to 5 \to 6 \to 9$, and add speed limits on the roads with indices $2,3,4,5,6,7,8,9,10,11,13,14,15,16$. Run the yellow light when arriving at $2,5$, pass directly on green when arriving at $4$, and wait $1$ second at a red light when arriving at $6$. Then $1 \to 2$ takes $1$ second, $2 \to 5$ takes $4$ seconds, $5 \to 6$ takes $9$ seconds, $6 \to 9$ takes $3$ seconds, plus the $1$ second waiting for the red light, for a total of $18$ seconds.

Translated by ChatGPT 5