프로세서

현재 생산되는 대부분의 프로세서는 멀티코어, 즉 여러 명령을 동시에 실행할 수 있다. Paraltel 사는 대문자 라틴 문자로 표시되는 26가지 명령을 실행할 수 있는 새로운 유형의 듀얼코어 프로세서를 개발했다. 각 명령의 실행에는 프로세서 클록이 정확히 1주기 걸린다.

이 프로세서를 위한 프로그램은 명령의 나열이다. 프로그램의 명령은 프로그램에 나오는 순서대로 실행해야 하며, 명령의 순서를 바꿀 수 없다.

코어가 두 개이므로 프로세서는 두 프로그램을 동시에 실행할 수 있다. 각 코어에서 하나씩 실행한다. 다만 구조상 같은 프로세서의 두 코어가 동시에 실행할 수 있는 것은 같은 명령뿐이다.

프로세서에서 두 프로그램을 실행할 때 전용 제어 장치가 두 프로그램을 최대한 빨리 끝내도록 실행을 최적화한다. 예를 들어 프로그램 "ABB"와 "ABC"는 프로세서에서 4주기에 실행할 수 있다. 먼저 두 프로그램의 "A" 명령이 서로 다른 코어에서 동시에 실행되고, 다음으로 "B" 명령이 동시에, 그다음 첫 번째 프로그램의 "B"가, 마지막으로 두 번째 프로그램의 "C"가 실행된다. 마찬가지로 프로그램 "CAB"와 "BAB"는 4주기에 실행된다.

최근 회사 기술자들은 n개의 프로세서로 슈퍼컴퓨터를 조립했고, 여기서 2n개의 프로그램을 실행해야 한다. 계산 구성상 각 프로세서는 이 집합에서 정확히 두 프로그램을, 각 코어에 하나씩 실행해야 한다.

n개의 프로세서에서 2n개의 프로그램을 실행하는 일정을, 모든 프로그램의 실행이 끝나는 시각이 최소가 되도록 세워야 한다.

첫째 줄에 수 n (1 ≤ n ≤ 10)이 주어진다. 이는 프로세서의 개수이다. 이어서 2n개의 줄에 실행해야 하는 프로그램이 주어진다. 각 프로그램은 1개 이상 100개 이하의 명령을 포함한다. 각 명령은 대문자 라틴 문자로 주어진다.

모든 프로그램을 실행할 수 있는 최소 시간을 나타내는 수 하나를 출력한다.