하버드 구조

"하버드 구조(Harvard architecture)"는 명령어와 데이터를 물리적으로 분리된 메모리에 저장하는 컴퓨터를 가리킨다. 이 이름은 1944년 IBM이 제작한 Harvard Mark I 컴퓨터에서 유래했으며, 이 컴퓨터는 명령어를 종이 테이프에, 데이터를 릴레이에 저장했다.

일부 현대 마이크로컨트롤러도 (종이 테이프와 릴레이는 아니지만) 하버드 구조를 사용한다. 데이터 메모리는 여러 개의 뱅크(bank)로 나뉘고, 모든 뱅크는 같은 개수의 데이터 항목을 담는다. 데이터를 참조하는 각 명령어는 뱅크 안에서의 바이트 오프셋 $f$ 와, 어느 뱅크를 참조할지 고르는 비트 $a$ 를 가진다.

• $a = 0$ 이면 $0$ 번 뱅크를 참조한다.
• $a = 1$ 이면 뱅크 선택 레지스터(BSR)에 들어 있는 값이 참조할 뱅크를 정한다.

모든 명령어의 실행 시간은 같다고 가정하고, BSR에 값을 넣는 별도의 명령어가 있다고 하자.

예를 들어 각 $8$ 바이트짜리 뱅크가 $4$ 개 있다고 하자. 위치 $5$ 에 접근하려면, $a = 0$, $f = 5$ 인 명령어 하나만 쓰거나, 먼저 BSR을 $0$ 으로 설정한 뒤 $a = 1$, $f = 5$ 인 명령어를 쓸 수 있다. 앞의 방법이 BSR 설정이 필요 없으므로 더 빠르다.

같은 메모리에서 이번에는 위치 $20$ 에 접근한다고 하자. 이때는 한 가지 방법뿐이다. BSR을 $2$ 로 설정하고(이미 $2$ 라면 생략) $a = 1$, $f = 4$ 인 명령어를 실행한다.

프로그램은 연산들의 나열이다. 각 연산은 다음 중 하나이다.

• 변수 참조: $V_i$ 로 쓰며, $i$ 는 양의 정수이다.
• 반복: $R_n\ \langle P\rangle\ E$ 로 쓰며, $n$ 은 양의 정수이고 $P$ 는 임의의 프로그램이다. 이는 $P$ 를 연달아 $n$ 번 실행하는 것과 같다.

각 뱅크에 담을 수 있는 변수 개수 한도를 지키는 한, 변수를 어느 뱅크에 배치할지는 자유롭게 정할 수 있다. 뱅크의 개수와 크기, 그리고 실행할 프로그램이 주어졌을 때, 실행 시간을 최소로 만드는 배치를 골라 그 실행 시간, 즉 실행되는 명령어의 총개수(메모리 참조 횟수와 BSR 설정 횟수의 합)를 구하라. BSR의 초기값은 정해져 있지 않으며, 명령어가 명시적으로 값을 넣을 때만 바뀐다.

입력은 하나의 테스트 케이스이며 두 줄로 이루어진다. 첫 줄에는 두 정수 $b$ 와 $s$ 가 주어진다($1 \le b \le 13$, $1 \le s \le 13$). $b$ 는 메모리 뱅크의 개수, $s$ 는 한 뱅크에 담을 수 있는 변수의 개수이다. 둘째 줄에는 공백으로 구분된 원소가 최대 $1000$ 개인, 비어 있지 않은 프로그램이 주어진다(각 $R_n$, $V_i$, $E$ 가 원소 하나로 센다).

다음을 가정해도 좋다.

• 반복 $R_n$ 에서 $1 \le n \le 10^6$ 이다.
• 반복 $R_n\ \langle P\rangle\ E$ 에서 본문 $P$ 는 비어 있지 않다.
• 변수 참조 $V_i$ 에서 $1 \le i \le \min(b \cdot s, 13)$ 이다.
• 프로그램을 한 번 실행할 때 수행되는 변수 참조의 총횟수는 최대 $10^{12}$ 이다.

프로그램을 실행하는 데 필요한 명령어의 최소 개수를 출력하라.