HZNUOJ

Longest Prefix

Tags:
Time Limit:  10 s      Memory Limit:   128 MB
Submission:0     AC:0     Score:100.00

Description

The structure of some biological objects is represented by the sequence of their constituents. These constituents are denoted by uppercase letters. Biologists are interested in decomposing a long sequence into shorter ones. These short sequences are called primitives. We say that a sequence S can be composed from a given set of primitives P, if there are n primitives p1,...,pn in P such that the concatenation p1...pn of the primitives equals S. By the concatenation of primitives p1,...,pn  we mean putting them together in that order without blanks.  The same primitive can occur more than once in the concatenation and not necessarily all primitives are present. For instance the sequence ABABACABAAB can be composed from the set of primitives

       {A, AB, BA, CA, BBC}.

The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives P and a sequence of constituents T. The program must compute the length of the longest prefix, that can be composed from primitives in P. 

Input

The first line contains N, the number of primitives in P (1<=N<=100). Each primitive is given in two consecutive lines. The first line contains the length L of the primitive (1<=L<=20). In the second line there is a string of uppercase letters (from 'A' to 'Z') of length L. The N primitives are all different.

After a blank line are DATA, and each line of the DATA contains one uppercase letter in the first position. This file ends with a line containing a single period ('.').

The length of the DATA is at least 1 and at most 500,000.

Output

The length of the longest prefix of T that can be composed from the set P.

Samples

input
5 1 A 2 AB 3 BBC 2 CA 2 BA A B A B A C A B A A B C B .
output
11

Source

IOI1996 Day2