本题没有可用的提交语言。

题目描述

著名半导体公司Outel最近发布了一款名为Platinium的新型微处理器。与许多现代处理器一样，Platinium可以在一个时钟周期内并行执行多条指令，前提是这些指令之间没有依赖关系（例如，如果指令I2读取了指令I1写入的寄存器，则I2依赖于I1）。有些处理器非常智能，能够动态计算哪些指令可以安全地并行执行。然而，Platinium要求显式指定这些信息。在两条指令之间插入的特殊标记称为“停止”（stop），表示在停止之后的某些指令可能依赖于停止之前的某些指令。换句话说，两个连续停止之间的指令可以并行执行，且它们之间不应存在依赖关系。

Platinium的另一个有趣特性是指令序列必须分成由1、2或3条连续指令组成的组。每组必须打包到一个称为“束”（bundle）的容器中。每个束有3个槽位，每条指令可以放入一个槽位中，但某些槽位可能为空。每条指令被分类为10种指令类型之一，用连续的大写字母A到J表示（相同类型的指令具有相似的功能，例如类型A包括整数算术指令，类型F包括浮点指令等）。只有某些类型的指令才允许被打包到同一个束中。一个“模板”（template）指定了束中允许的指令类型组合。模板还可以指定束中间的一个停止位置（最多允许一个停止）。此外，停止允许在任何两个相邻的束之间插入。模板的集合称为“捆绑配置文件”（bundling profile）。在将指令打包到束中时，只能使用捆绑配置文件中的模板。

尽管Platinium配备了指令缓存，但研究发现，为了最大化性能，最关键的是尽可能密集地打包指令。其次重要的是使用较少数量的停止。

你的任务是为Platinium指令编写一个捆绑程序。为了简单起见，我们假设指令不能重新排序。

任务

编写一个程序，完成以下任务：

1. 读取一个捆绑配置文件和一条指令序列。
2. 计算在不破坏依赖关系的情况下，序列可以打包的最小束数量，以及在最小束数量下所需的最小停止总数。
3. 输出结果。

输入格式

输入的第一行包含两个整数t和n，用单个空格分隔。整数t（1 ≤ t ≤ 1500）是捆绑配置文件中的模板数量。整数n（1 ≤ n ≤ 100000）是要捆绑的指令数量。

接下来的t行每行指定一个模板，包含3个大写字母t1、t2、t3（无空格分隔），后跟一个空格和一个整数p。字母ti（A ≤ ti ≤ J）是允许在第i个槽位中的指令类型。整数p（0 ≤ p ≤ 2）是停止位置所在的槽位索引（0表示束内没有停止）。

接下来的n行每行指定一条指令。第i行包含一个大写字母ci和一个整数di，用单个空格分隔。字母ci（A ≤ ci ≤ J）是第i条指令的类型。整数di（0 ≤ di < i）是第i条指令依赖的最后一条指令的索引（0表示该指令不依赖于任何先前的指令）。

可以假设指令序列中每条指令的类型c至少有一个模板包含c。

输出格式

输出的第一行也是唯一一行包含两个整数b和s。整数b是有效打包的最小束数量。整数s是在最小束数量下所需的最小停止总数。

输入样例1

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

输出样例1

4 3

来源

Central Europe 2003