Bundling

Outel, a well-known semiconductor company, has recently released a new microprocessor called Platinium. Like many modern processors, Platinium can execute several instructions in a single clock step, provided that there are no dependencies among them (instruction I2 depends on instruction I1 if, for example, I2 reads a register that I1 writes to). Platinium does not discover parallelism on its own; this information must be stated explicitly. A special marker called a stop, placed between two instructions, indicates that some instructions after the stop may depend on some instructions before it. In other words, the instructions lying between two consecutive stops are executed in parallel, so there must be no dependency between any two of them.

In addition, the instruction sequence must be divided into groups of one, two, or three consecutive instructions, and each group is packed into a container called a bundle. A bundle has three slots; at most one instruction is placed in each slot, and some slots may stay empty. Each instruction has one of ten types, written as the capital letters A through J. Only certain type combinations may share a bundle. A template describes one permitted combination of slot types, and it may also fix the position of a single stop inside the bundle (at most one internal stop is allowed). Stops may additionally be placed between any two neighbouring bundles. The set of usable templates is called a bundling profile, and only templates from the profile may be used.

Packing the instructions as densely as possible is the most important goal; using as few stops as possible is the second goal. Instructions may not be reordered.

Write a program that reads a bundling profile and a sequence of instructions, and computes the minimum number of bundles into which the sequence can be packed without breaking any dependency, together with the minimum number of stops needed to reach that minimum number of bundles.

The first line contains two integers t and n separated by a single space. Integer t (1 ≤ t ≤ 1500) is the number of templates in the bundling profile, and integer n (1 ≤ n ≤ 100000) is the number of instructions to be bundled.

Each of the next t lines describes one template: three capital letters t1 t2 t3 with no spaces between them, followed by a space and an integer p. Letter ti (A ≤ ti ≤ J) is the instruction type allowed in the i-th slot. Integer p (0 ≤ p ≤ 2) is the index of the slot after which the internal stop is placed; p = 0 means the template has no internal stop.

Each of the next n lines describes one instruction: a capital letter ci and an integer di separated by a single space. Letter ci (A ≤ ci ≤ J) is the type of the i-th instruction, and di (0 ≤ di < i) is the index of the latest earlier instruction that the i-th instruction depends on; di = 0 means it depends on no earlier instruction.

You may assume that for every instruction type that appears in the sequence there is at least one template containing that type.

Print a single line with two integers b and s. Integer b is the minimum number of bundles in a valid packing, and integer s is the minimum number of stops required for that minimum number of bundles.