Bundling

Time Limit: 1 Second    Memory Limit: 32768 KB

Outel, a famous semiconductor company, released recently a new model of microprocessor called Platinium. Like many modern processors, Platinium can execute many instructions in one clock step providing that there are no dependencies between them (instruction I2 is dependent on instruction I1 if for example I2 reads a register that I1 writes to). Some processors are so clever that they calculate on the fly which instructions can be safely executed in parallel. Platinium however expects this information to be explicitly specified. A special marker, called simply a stop, inserted between two instructions indicates that some instructions after the stop are possibly dependent on some instructions before the stop. In other words instructions between two successive stops can be executed in parallel and there should not be dependencies between them.

Another interesting feature of Platinium is that a sequence of instructions must be split into groups of one, two or three successive instructions. Each group has to be packed into a container called a bundle. Each bundle has 3 slots and a single instruction can be put into each slot, however some slots may stay empty. Each instruction is categorized into one of 10 instruction types denoted by consecutive capital letters from A to J (instructions of the same type have silimar functionality, for example type A groups integer arithmetic instructions and type F groups floating-point instructions). Only instructions of certain types are allowed to be packed into one bundle. A template specifies one permissible combination of instruction types within a bundle. A template can also specify a position of a stop in the middle of a bundle (there is at most one such stop allowed). In addition, stops are allowed between any two adjoining bundles. A set of templates is called a bundling profile. When packing instructions into bundles, one has to use templates from bundling profile only.

Although Platinium is equipped with an instruction cache it was found that for maximal performance it is most crucial to pack instructions as densely as possible. Second important thing is to use a small number of stops.

Your task is to write a program for bundling Platinium instructions. For the sake of simplicity we assume that the instructions cannot be reordered.

Task

Write a program that:

• reads a bundling profile and a sequence of instructions,
• computes the minimal number of bundles into which the sequence can be packed without breaking the dependencies and the minimal number of all stops that are required for the minimal number of bundles,
• writes the result.

Input

The input consists of several test cases.
For each case, the first line contains two integers T and N separated by a single space. Integer T (1 <= T <= 1 500) is the number of templates in the bundling profile. Integer N (1 <= N <= 100 000) is the number of instructions to be bundled.
Each of the next T lines specifies one template and contains 3 capital letters T1, T2, T3 with no spaces in between followed by a space and an integer P. Letter Ti (A <= Ti <= J) is an instruction type allowed in the i-th slot. Integer P (0 <= P <= 2) is the index of the slot after which the stop is positioned (0 means no stop within the bundle).
Each of the next N lines specifies one instruction. The i-th line of these N lines contains one capital letter Ci and an integer Di (0 <= Di < i) is the index of the last instruction (among the previous ones) that the i-th instruction is dependent on (0 means that the instruction is not dependent on any former instruction).
You can assume that for each instruction type C appearing in the instruction sequence there is at least one template containing C.

Output

For each test case, print in one line two integers B and S separated by a single space. Integer B is the minimal number of bundles in a valid packing. Integer S is the minimal number of all stops that are required for the minimal number of bundles.

Sample Input

4 9
ABB 0
BAD 1
AAB 0
ABB 2
B 0
B 1
A 1
A 1
B 4
D 0
A 0
B 3
B 0

Sample Output

4 3

Submit

Source: Central Europe 2003