Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Hyper String

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPaul Erdős's prediction came true. Finally an alien force landed on the Earth. In contrary to our expectation they didn't asked the humans to compute the value of a Ramsey number (maybe they had solved it themselves). They asked another question which seemed as hard as calculating Ramsey numbers. Aliens threatened that if humans don't solve this problem in less than 2 hours they will destroy the Earth.

Before telling the problem they introduced the concept of Hyper Strings. A Hyper String is made by concatenation of some base strings. Suppose you are given a list of base strings *b* _{1}, *b* _{2}, ..., *b* _{ n}. Now the Hyper String made from indices list *i* _{1}, *i* _{2}, ..., *i* _{ m} is concatenation of base strings *b* _{ i 1}, *b* _{ i 2}, ..., *b* _{ i m}. A Hyper String can be very large and doing operations on it is very costly for computers.

The aliens asked humans to compute the length of the longest common sub-sequence of a Hyper String *t* with a string *s*.

Input

The first line of input contains the single integer *n* (1 ≤ *n* ≤ 2000) — the number of base strings.

The next *n* lines contains values of base strings. Each base string is made of lowercase Latin letters. A base string cannot be empty string and the sum of lengths of all *n* base strings doesn't exceed 10^{6}.

The next line contains the single integer *m* (1 ≤ *m* ≤ 2000) — the number of base strings in the given Hyper String *t*.

The next line contains *m* space-separated integer numbers *i* _{1}, *i* _{2}, ..., *i* _{ m} (1 ≤ *i* _{ j} ≤ *n*) — the indices of base strings in the Hyper String *t*.

The last line contains a non-empty string *s*. String *s* is made of lowercase Latin letters and its length is no more than 2000 characters.

Output

Print the length of longest common sub-sequence of Hyper String *t* and string *s*. If there is no common sub-sequence print 0.

Examples

Input

2

cba

dgh

2

1 2

aedfhr

Output

3

Input

2

b

a

5

1 2 1 2 1

aaa

Output

2

Note

The length of string *s* is the number of characters in it. If the length of string *s* is marked as |*s*|, then string *s* can be represented as *s* = *s* _{1} *s* _{2}... *s* _{|s|}.

A non-empty string *y* = *s*[*p* _{1} *p* _{2}... *p* _{|y|}] = *s* _{ p 1} *s* _{ p 2}... *s* _{ p |y|} (1 ≤ *p* _{1} < *p* _{2} < ... < *p* _{|y|} ≤ |*s*|) is a subsequence of string *s*. For example, "coders" is a subsequence of "codeforces".

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/09/2020 15:19:45 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|