A. Garbage (1000 points)

We have N cities (numbered 1-N) and bidirectional roads between them. Each road has a length. Some cities have recycle plants which are able to recycle some types of garbage. There are 26 types of garbage (a-z).

The task is to recycle a garbage-string while we have to minimize the total moving cost. The moving cost of a garbage-string is equal to the length of the road (independently from the length of the garbage). We can cut a string into several smaller strings anywhere, but multiple strings cannot be attached to form one longer. We can recycle a string at a city if it contains only the kind of gargabe that can be recycled there.

Input

Each input contains multiple test cases, each test case looks like this:

First line: N M L S (number of cities, number of roads, length of initial garbage string, starting city of the garbage)

Next N lines: k_i t_i (t_i is a k_i characters long string specifying the types of garbages that the ith city can recycle)

Next M lines: a_j b_j w_j (road between cities a and b with length w)

Last line: g (the garbage string (L characters long))

After the last test case, there will be "0 0 0 0" in the last line.

Output

For each test case output the minimal total cost on a separate line, or -1 if the test case is not solvable.

Sample input

3 2 6 1
1 a
1 b
2 cb
1 2 1
2 3 2
abbcab
0 0 0 0

Sample output

4