DuLL

In Windows, a DLL (dynamic link library) is a file that contains a collection of pre-compiled functions that can be loaded into a program at runtime. The two primary benefits of DLLs are (1) only one copy of a DLL is needed in memory, regardless of how many different programs use it at the same time, and (2) since they are separate from programs, DLLs can be upgraded independently, without having to recompile the programs that use them.

The DLLs in our system are not very exciting. These dull DLLs (or DuLLs) each require a fixed amount of memory that never changes while the DuLL is in memory. Similarly, each program has its own fixed memory requirement that never changes while the program is executing. Each program also requires certain DuLLs to be in memory the entire time the program is executing. Therefore, the only time the amount of required memory changes is when a new program is executed or a currently running program exits. When a new program begins execution, all DuLLs it requires that are not already in memory are loaded. When a currently running program exits, all DuLLs that are no longer needed by any currently running program are removed from memory.

There is never more than one copy of a specific DuLL in memory at any given time. However, it is possible for multiple instances of the same program to run at the same time. In that case each instance requires its own memory, but the instances still share DuLLs in the same way two unrelated programs would.

Given a series of programs run together with the DuLLs they need, compute the maximum memory usage over the whole execution. At any moment the memory usage is (the sum of the sizes of all currently running program instances) plus (the sum of the sizes of all DuLLs currently in memory).

The input consists of one or more data sets, followed by a line containing only 0.

The first line of a data set contains three space-separated integers $N$, $P$, $S$, where $N$ is the number of available DuLLs ($1 \le N \le 20$), $P$ is the number of programs that can be executed ($1 \le P \le 9$), and $S$ is the number of recorded state transitions ($1 \le S \le 32$).

The next line contains exactly $N$ space-separated integers giving the sizes in bytes of the DuLLs ($1 \le \text{size} \le 1000$). Each DuLL is implicitly labeled with a letter 'A', 'B', 'C', …, up to at most 'T'. Thus the first integer is the size of 'A', the second is the size of 'B', and so on.

The next $P$ lines describe the programs, one per line. Each line starts with a single integer, the size of the program in bytes ($1 \le \text{size} \le 1000$), followed by $1$ to $N$ characters naming the DuLLs that program requires. There is a single space between the program size and the DuLL labels, but no spaces between the labels themselves. The order of the labels is insignificant; they are all valid DuLL labels and no label occurs more than once. Each program is implicitly labeled with an integer 1, 2, 3, …, up to at most 9.

The last line of a data set contains $S$ space-separated integers. Each integer is either a positive number $q$ ($1 \le q \le P$), meaning a new execution of program $q$ has begun, or a negative number $-q$ ($1 \le q \le P$), meaning a single execution of program $q$ has completed. The transitions are given in the order they occurred. Every value is a valid program number, and whenever a value is $-q$ there is always at least one instance of program $q$ running at that time.

Print one line for each data set, containing only the maximum amount of memory required throughout the execution of that data set.