El término «arquitectura Harvard» se aplica a un ordenador que tiene memorias físicamente separadas para las instrucciones y los datos. El término se originó con el ordenador Harvard Mark I, entregado por IBM en 1944, que utilizaba cinta de papel para las instrucciones y relés para los datos.

Algunos microcontroladores modernos utilizan la arquitectura Harvard, ¡pero no cinta de papel ni relés! La memoria de datos se organiza en bancos, cada uno con el mismo número de elementos de datos. Cada instrucción que referencia datos tiene un desplazamiento en bytes $f$ dentro de un banco y un bit $a$ utilizado para seleccionar el banco que se referencia. Si $a$ es $0$, se referencia el banco $0$. Si $a$ es $1$, el valor de un registro de selección de banco (BSR) identifica el banco que se utilizará. Supón que todas las instrucciones tardan lo mismo en ejecutarse y que existe una instrucción que puede establecer el valor del BSR.

Imagen de Wikimedia Commons

Por ejemplo, supón que hay 4 bancos de 8 bytes cada uno. Para acceder a la posición $5$, puedes usar una sola instrucción con $a = 0$ y $f = 5$, o establecer el BSR a $0$ con una instrucción y luego usar otra con $a = 1$ y $f = 5$. El primer método es más rápido porque no requiere establecer el BSR.

Ahora supón que, con la misma memoria, la posición a la que se quiere acceder es $20$. Aquí solo funciona un método: ejecutar una instrucción que establezca el BSR a $2$ (a menos que ya tenga el valor $2$) y después usar una instrucción con $a = 1$ y $f = 4$.

Un programa es una secuencia de operaciones. Cada operación es una de las siguientes:

• una referencia a una variable, escrita como Vi, donde $i$ es un entero positivo, o

• una repetición, escrita como Rn <program> E, donde $n$ es un entero positivo y <program> es un programa arbitrario. Esta operación equivale a $n$ apariciones consecutivas de <program>.

Tu problema es determinar el tiempo mínimo de ejecución de los programas. En particular, dados el número y el tamaño de los bancos de memoria y un programa que se debe ejecutar, encuentra el número mínimo de instrucciones (que referencian posiciones de memoria y posiblemente establecen el BSR) que deben ejecutarse para realizar el programa. Para ello, debes identificar una asignación de variables a bancos que produzca el menor tiempo de ejecución e informar de ese tiempo: el número de referencias a memoria y de ajustes del registro BSR necesarios. El valor del BSR es inicialmente indefinido y solo cambia cuando una instrucción lo establece explícitamente.

Entrada

La entrada consta de un único caso de prueba de dos líneas. La primera contiene dos enteros $b$ y $s$, donde $1 \le b \le 13$ es el número de bancos de memoria y $1 \le s \le 13$ es el número de variables que se pueden almacenar en cada banco. La segunda contiene un programa no vacío con como máximo 1 000 elementos separados por espacios (cada Rn, Vi y E cuenta como un elemento).

Puedes suponer lo siguiente:

• En una repetición Rn, el número de repeticiones satisface $1 \le n \le 10^6$.

• En una operación de bucle Rn <program> E, el cuerpo <program> no está vacío.

• En una referencia a variable Vi, el índice de la variable satisface $1 \le i \le \min(b \cdot s, 13)$.

• El número total de referencias a variables realizadas al ejecutar el programa es como máximo $10^{12}$.

Salida

Muestra el número mínimo de instrucciones que deben ejecutarse para completar el programa.

Ejemplos

Entrada 1

1 2
V1 V2 V1 V1 V2

Salida 1

5

Entrada 2

2 1
V1 V2 V1 V1 V2

Salida 2

6

Entrada 3

1 2
R10 V1 V2 V1 E

Salida 3

30

Entrada 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Salida 4

17