Description

牛逼的学生总会对提早毕业感兴趣，大学会为该生提供一系列课程，包括课程的前提课程（只有得到全部前提课程的学分才可学习该门课程）和开课季度。得到这些信息后，可以计算出最少上几个学期的课就可以毕业。 考虑下面的例子，一个学生需要上4门课，mt42, cs123, cs456和cs789。mt42只在秋季开课，没有前提课程。cs123只在春季开课，没有前提课程。cs456只在春季开课，cs123和mt42是它的前提课程。cs789在春季和秋季都有开课，cs456是它的前提课程。最短可以毕业的时间是5个学期，秋季上mt42，下个春季上cs123，下个秋季不上课，下个春季上cs456，下个秋季上完cs789就可以毕业。 在本题中，只有两种学期，春季和秋季，每个新生的第一个学期总是秋季。 为了保证教学，大学限制每个学生每个学期最多可修的课程数，在输入数据中会给出相关的数值。

Input

输入包含多组数据，以-1 -1结束。 每组数据的第一行是两个整数n和m，n代表课程总数（1 ≤ n ≤ 12），m代表每学期最多可修的课程数（2 ≤ m ≤ 6）。 接下去的一行包含n个字符串，分别表示n门课程的名称。 最后有n行分别给出n个课程的信息，每行表示一个课程，包括课程名（长度为1-5，包含字符{a-z, 0-9}），开课季度（F代表秋季，S代表春季，B代表每个季度都开课），该课程的前提课程数目p（0 ≤ p ≤ 5），最后p个是前提课程的课程名。

Output

输出按Sample Output的格式输出。

Sample

Input

4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1

Output

The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.