Rabbit’s Cheating Strategy

In this problem, a rabbit named Stan and a turtle named George compete in a race on a graph. The race graph has (N) vertices and (M) directed edges. The race starts at vertex 1 and ends at vertex (N). Before the race begins, both Stan and George select a route. George runs along his chosen path exactly as planned, but along the way he chooses some vertices at which he takes a nap (each nap lasts a fixed time (L)). However, if at any moment George is awake and notices that Stan has deviated from his pre‐chosen path (i.e. is cheating), then George immediately stops napping (or, if currently napping, he will wake as soon as his nap ends) and continues the race without any further delay.

Stan, the rabbit, has a cunning plan. He will follow his selected path until, upon arriving at some vertex (v) (with (v \neq N)), he decides to cheat by switching his route to the shortest path (in terms of total travel time) from (v) to (N). However, Stan must choose his cheating moment wisely: if he deviates at a time when George is awake, George will immediately be alerted and finish the race faster (since he will forgo any future naps). If, however, George is napping at the moment of deviation, then George only finds out after waking up – which might be too late for George to beat Stan.

Given the full graph and the travel time on each edge, you are provided with the following additional information:

• The fixed nap duration \(L\) for George.
• Stan’s pre‐selected path (a sequence of vertices starting at 1 and ending at \(N\)).
• George’s pre‐selected path (a sequence of vertices starting at 1 and ending at \(N\)).
• A set of indices (1-indexed) along George’s path where he takes a nap. (George does not nap at the final vertex \(N\).)

Stan’s arrival time at each vertex on his path can be computed by summing the travel times along the edges in his path. If he deviates at vertex \(v\) (at time \(T_{\text{Stan}}(v)\)) then his finish time is: \[ T_{\text{Stan}}^{*}(v) = T_{\text{Stan}}(v) + d(v, N), \] where \(d(v,N)\) denotes the shortest travel time from vertex \(v\) to vertex \(N\) in the given graph (this must be computed using, for example, Dijkstra’s algorithm).

George’s race is simulated based on his chosen path. Assume that in his no‐alert schedule (i.e. if he never gets alerted by Stan cheating) his finish time is \(T_{\text{George}}^{\text{noalert}}\). His schedule is constructed as follows: starting at time 0, for each segment along his path, if the current vertex is one where he naps, he sleeps for \(L\) time (thus delaying his progress) and then traverses the next edge; otherwise, he immediately traverses the edge. If Stan deviates at time \(A\) and George is awake at that moment, then George is alerted and will cancel all future naps. In that case, if George has covered a total "distance" (i.e. sum of travel times on edges as if no naps occurred) of \(D\) by time \(A\), then his new finish time becomes: \[ T_{\text{George}} = A + \Bigl( D_{\text{total}} - D \Bigr), \] where \(D_{\text{total}}\) is the total travel time for George’s path ignoring naps, and the remaining travel time is computed without any further nap delays. Note that if \(A\) falls within one of George’s nap intervals, then George is considered to be sleeping at the moment of cheating and he is not alerted instantly; in that case, his finish time remains \(T_{\text{George}}^{\text{noalert}}\).

Your task is to compute the number of vertices (i.e. the number of possible departure times along Stan’s path, excluding the final vertex) at which Stan can choose to deviate so that his finish time is strictly less than George’s finish time. In other words, count the number of indices \(i\) (with the \(i\)th vertex on Stan’s path, \(i \lt S\)) such that \[ T_{\text{Stan}}(i) + d(\text{Stan}[i], N)

inputFormat

The input begins with three integers \(N\), \(M\) and \(L\) \( (2 \le N \le 10^5, \, 1 \le M \le 10^5, \, 1 \le L \le 10^9)\), representing the number of vertices, the number of edges, and the fixed nap duration for George.

Then \(M\) lines follow, each containing three integers \(u\), \(v\), \(t\) \( (1 \le u,v \le N, \, 1 \le t \le 10^9)\) representing a directed edge from vertex \(u\) to vertex \(v\) with travel time \(t\). It is guaranteed that for any edge used in the given paths, an edge exists in the graph.

The next line contains an integer \(S\) \((2 \le S \le 10^5)\) representing the number of vertices in Stan’s pre-selected path.

The following line contains \(S\) space-separated integers representing Stan’s path (the first integer is 1 and the last is \(N\)).

The next line contains an integer \(G\) \((2 \le G \le 10^5)\) representing the number of vertices in George’s pre-selected path.

The following line contains \(G\) space-separated integers representing George’s path (the first integer is 1 and the last is \(N\)).

The next line contains an integer \(K\) \((0 \le K < G)\) representing the number of positions (1-indexed along George’s path, excluding the final vertex) at which George takes a nap.

The last line contains \(K\) space‐separated integers. Each integer is an index \(i\) (with \(1 \le i \lt G\)) indicating that George sleeps at the \(i\)th vertex of his path.

outputFormat

Output a single integer: the number of vertices on Stan’s path (excluding the final vertex) at which if Stan deviates (i.e. cheats) he will finish the race strictly before George.

sample

5 6 5
1 2 3
2 3 4
3 5 5
1 4 10
4 5 1
2 5 100
4
1 2 3 5
4
1 2 4 5
2
2 3

1

</p>