번들링

유명한 반도체 회사 Outel이 최근 Platinium이라는 새 마이크로프로세서를 출시했다. 많은 최신 프로세서처럼 Platinium은 명령어 사이에 의존성이 없다면 한 클록 스텝에 여러 명령어를 동시에 실행할 수 있다(예를 들어 명령어 I2가 I1이 쓰는 레지스터를 읽는다면, I2는 I1에 의존한다). Platinium은 병렬성을 스스로 찾아내지 않으므로 이 정보를 명시적으로 지정해 주어야 한다. 두 명령어 사이에 놓는 스톱(stop)이라는 특수한 표시는, 스톱 뒤의 일부 명령어가 스톱 앞의 일부 명령어에 의존할 수 있음을 나타낸다. 다시 말해 연속한 두 스톱 사이에 있는 명령어들은 병렬로 실행되므로, 그 명령어들 사이에는 어떤 의존성도 있어서는 안 된다.

또한 명령어 수열은 연속한 한 개, 두 개, 또는 세 개의 명령어로 이루어진 그룹으로 나뉘어야 하며, 각 그룹은 번들(bundle)이라는 용기에 담긴다. 번들에는 슬롯이 세 개 있고, 각 슬롯에는 명령어를 최대 하나 넣을 수 있으며 일부 슬롯은 비어 있어도 된다. 각 명령어는 열 가지 종류 중 하나이며, 대문자 A부터 J까지로 표기한다. 특정한 종류 조합만이 한 번들에 함께 들어갈 수 있다. 템플릿(template)은 허용되는 슬롯 종류 조합 하나를 기술하며, 번들 내부에 스톱 하나의 위치를 지정할 수도 있다(내부 스톱은 최대 한 개만 허용된다). 스톱은 이웃한 두 번들 사이에도 추가로 놓을 수 있다. 사용할 수 있는 템플릿의 집합을 번들링 프로파일(bundling profile)이라고 하며, 프로파일에 있는 템플릿만 사용할 수 있다.

명령어를 최대한 촘촘하게 담는 것이 가장 중요한 목표이고, 스톱을 최대한 적게 쓰는 것이 그다음 목표다. 명령어의 순서는 바꿀 수 없다.

번들링 프로파일과 명령어 수열을 읽어, 어떤 의존성도 깨뜨리지 않고 수열을 담을 수 있는 최소 번들 수와, 그 최소 번들 수를 이루는 데 필요한 최소 스톱 수를 계산하는 프로그램을 작성하라.

첫 줄에는 공백으로 구분된 두 정수 t와 n이 주어진다. 정수 t (1 ≤ t ≤ 1500)는 번들링 프로파일에 있는 템플릿의 수이고, 정수 n (1 ≤ n ≤ 100000)은 번들링할 명령어의 수이다.

이어지는 t개의 줄에는 각각 템플릿 하나가 주어진다. 공백 없이 붙은 세 대문자 t1 t2 t3 뒤에 공백 하나와 정수 p가 온다. 문자 ti (A ≤ ti ≤ J)는 i번째 슬롯에 허용되는 명령어 종류이다. 정수 p (0 ≤ p ≤ 2)는 내부 스톱이 놓이는 슬롯의 번호로, 그 슬롯 뒤에 스톱이 위치한다. p = 0이면 템플릿에 내부 스톱이 없다는 뜻이다.

이어지는 n개의 줄에는 각각 명령어 하나가 주어진다. 공백으로 구분된 대문자 ci와 정수 di가 온다. 문자 ci (A ≤ ci ≤ J)는 i번째 명령어의 종류이고, 정수 di (0 ≤ di < i)는 i번째 명령어가 의존하는, 앞선 명령어 중 가장 나중 것의 번호이다. di = 0이면 어떤 앞선 명령어에도 의존하지 않는다는 뜻이다.

명령어 수열에 등장하는 모든 명령어 종류에 대해, 그 종류를 포함하는 템플릿이 적어도 하나 존재한다고 가정해도 된다.

두 정수 b와 s를 한 줄에 출력한다. 정수 b는 올바른 배치에서의 최소 번들 수이고, 정수 s는 그 최소 번들 수에 필요한 최소 스톱 수이다.