Beware the Geoducks

Time limit1sMemory limit128 MB

Summary

Given two fixed walking routes on a weighted graph, decide whether the two travelers ever occupy the same point within t seconds, accounting for nodes with geoducks that make a traveler vanish.

Level: Hard8 of 10
Topics: Implementation, Simulation, Geometry, Math
Solved: No attempts yet

Problem

Stan Velikiy is once again chasing his arch-nemesis, Mario the Wabbit, this time around a circuit. As the amused observer, you have been asked to predict the outcome.

The circuit is a set of nodes connected by wires of given lengths. Stan and Mario each start at one node and follow a predetermined route: a list of nodes visited in order, moving along the wires at a speed of one meter per second. Consecutive nodes in a route are always joined directly by a wire. When a traveler's route runs out, they stay at that final node forever.

If Stan and Mario are ever at the exact same location at the same instant — the same node, or the same point along a wire — Stan apprehends Mario. If more than $t$ seconds pass without a capture, Stan gives up.

Unknown to both, geoducks sit at some of the nodes. Anyone who reaches a node holding a geoduck vanishes instantly, and once either Stan or Mario vanishes, Stan can never catch Mario. In particular, if the two meet exactly on a node that holds a geoduck, they both vanish and it does not count as a capture.

Input

The first line contains six integers: $V$ ( $0 \le V \le 100$ ), the number of nodes; $E$ ( $0 \le E \le 1000$ ), the number of wires; $S$ and $M$ ( $1 \le S, M \le 1000$ ), the number of nodes in Stan's and Mario's routes, respectively; $G$ ( $0 \le G \le 100$ ), the number of geoducks; and $t$ ( $0 \le t \le 1000$ ), the time limit in seconds.

Each of the next $E$ lines contains three integers: the two nodes that a wire connects and its length $l$ ( $1 \le l \le 2000$ ). No wire connects a node to itself, and there is at most one wire between any two nodes.

The next $S$ lines each contain one integer, giving the nodes of Stan's route in the order they are visited.

The next $M$ lines each contain one integer, giving the nodes of Mario's route in the order they are visited.

The final $G$ lines each contain one integer, giving a node that holds a geoduck.

Output

Print YES if Stan catches Mario no later than $t$ seconds after the start, and NO otherwise.

Note

As an illustration, suppose Stan walks from node 1 toward node 2 while Mario walks from node 2 toward node 1 along the same wire, with a geoduck resting on an unrelated node 3 that neither traveler ever reaches. The two meet in the middle of that wire; even if they arrive there exactly when the time limit is reached, Stan still catches Mario.

Examples3

Example 1
Input
```
3 1 2 2 1 3
1 2 6
1
2
2
1
3
```
Expected output
```
YES
```
Example 2
Input
```
2 1 1 1 0 0
1 2 5
1
1
```
Expected output
```
YES
```
Example 3
Input
```
2 1 2 2 0 3
1 2 5
1
2
2
1
```
Expected output
```
YES
```