O termo “arquitetura Harvard” se aplica a um computador que tem memórias fisicamente separadas para instruções e dados. O termo surgiu com o computador Harvard Mark I, entregue pela IBM em 1944, que usava fita de papel para instruções e relés para dados.

Alguns microcontroladores modernos usam a arquitetura Harvard, mas não fita de papel e relés! A memória de dados é organizada em bancos, cada um contendo a mesma quantidade de itens de dados. Cada instrução que referencia dados tem um deslocamento em bytes $f$ dentro de um banco e um bit $a$ usado para selecionar o banco referenciado. Se $a$ for $0$, o banco $0$ é referenciado. Se $a$ for $1$, o valor de um registrador de seleção de banco (BSR) identifica o banco a ser usado. Suponha que todas as instruções levem o mesmo tempo para executar e que exista uma instrução capaz de definir o valor do BSR.

Imagem de Wikimedia Commons

Por exemplo, suponha que haja 4 bancos de 8 bytes cada. Para acessar a posição $5$, use uma única instrução com $a = 0$ e $f = 5$, ou defina o BSR como $0$ em uma instrução e depois use uma instrução com $a = 1$ e $f = 5$. A primeira abordagem é mais rápida porque não exige definir o BSR.

Agora suponha que, com a mesma memória, a posição a acessar seja $20$. Só uma abordagem funciona aqui: execute uma instrução que defina o BSR como $2$ (a menos que seu valor já seja $2$) e depois use uma instrução com $a = 1$ e $f = 4$.

Um programa é uma sequência de operações. Cada operação é uma das seguintes:

• uma referência a variável, escrita como Vi, onde $i$ é um inteiro positivo, ou

• uma repetição, escrita como Rn <program> E, onde $n$ é um inteiro positivo e <program> é um programa arbitrário. Essa operação equivale a $n$ ocorrências sequenciais de <program>.

Seu problema é determinar o menor tempo de execução dos programas. Em particular, dados o número e o tamanho dos bancos de memória e um programa a ser executado, encontre o número mínimo de instruções (que referenciam posições de memória e possivelmente definem o BSR) que devem ser executadas para realizar o programa. Para isso, identifique uma atribuição de variáveis a bancos que produza o menor tempo de execução e informe esse tempo: a quantidade de referências à memória e de definições do registrador BSR necessárias. O valor inicial do BSR é indefinido e só muda quando uma instrução define explicitamente seu valor.

Entrada

A entrada consiste em um único caso de teste com duas linhas. A primeira contém dois inteiros $b$ e $s$, onde $1 \le b \le 13$ é o número de bancos de memória e $1 \le s \le 13$ é a quantidade de variáveis que podem ser armazenadas em cada banco. A segunda contém um programa não vazio com no máximo 1 000 elementos separados por espaços (cada Rn, Vi e E conta como um elemento).

Você pode supor o seguinte:

• Em uma repetição Rn, a quantidade de repetições satisfaz $1 \le n \le 10^6$.

• Em uma operação de laço Rn <program> E, o corpo <program> não está vazio.

• Em uma referência a variável Vi, o índice da variável satisfaz $1 \le i \le \min(b \cdot s, 13)$.

• A quantidade total de referências a variáveis realizadas em uma execução do programa é no máximo $10^{12}$.

Saída

Exiba o número mínimo de instruções que devem ser executadas para concluir o programa.

Exemplos

Entrada 1

1 2
V1 V2 V1 V1 V2

Saída 1

5

Entrada 2

2 1
V1 V2 V1 V1 V2

Saída 2

6

Entrada 3

1 2
R10 V1 V2 V1 E

Saída 3

30

Entrada 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Saída 4

17