Le terme « architecture Harvard » désigne un ordinateur possédant des mémoires physiquement distinctes pour les instructions et les données. Il vient de l’ordinateur Harvard Mark I, livré par IBM en 1944, qui utilisait une bande de papier pour les instructions et des relais pour les données.

Certains microcontrôleurs modernes utilisent l’architecture Harvard, mais pas de bande de papier ni de relais ! La mémoire de données est organisée en banques, contenant chacune le même nombre d’éléments de données. Chaque instruction référençant des données possède un décalage en octets $f$ dans une banque et un bit $a$ servant à sélectionner la banque à référencer. Si $a$ vaut $0$, la banque $0$ est référencée. Si $a$ vaut $1$, la valeur d’un registre de sélection de banque (BSR) identifie la banque à utiliser. Supposez que toutes les instructions prennent le même temps d’exécution et qu’une instruction permet de fixer la valeur du BSR.

Image provenant de Wikimedia Commons

Par exemple, supposez qu’il y ait 4 banques de 8 octets chacune. Pour accéder à la position $5$, on peut utiliser une seule instruction avec $a = 0$ et $f = 5$, ou fixer le BSR à $0$ en une instruction, puis utiliser une instruction avec $a = 1$ et $f = 5$. La première méthode est plus rapide, car elle ne nécessite pas de modifier le BSR.

Supposez maintenant, avec la même mémoire, que la position à accéder soit $20$. Une seule méthode fonctionne : exécuter une instruction qui fixe le BSR à $2$ (sauf s’il vaut déjà $2$), puis utiliser une instruction avec $a = 1$ et $f = 4$.

Un programme est une suite d’opérations. Chaque opération est soit :

• une référence à une variable, écrite Vi, où $i$ est un entier positif, soit

• une répétition, écrite Rn <program> E, où $n$ est un entier positif et <program> un programme quelconque. Cette opération équivaut à $n$ occurrences successives de <program>.

Votre problème consiste à déterminer le temps d’exécution minimal des programmes. Plus précisément, étant donnés le nombre et la taille des banques de mémoire ainsi qu’un programme à exécuter, trouvez le nombre minimal d’instructions (qui référencent une position mémoire et éventuellement fixent le BSR) à exécuter pour réaliser le programme. Vous devez pour cela trouver une affectation des variables aux banques minimisant le temps d’exécution et indiquer ce temps, c’est-à-dire le nombre de références mémoire et de modifications du registre BSR nécessaires. La valeur du BSR est initialement indéfinie et ne change que lorsqu’une instruction la fixe explicitement.

Entrée

L’entrée consiste en un seul cas de test de deux lignes. La première contient deux entiers $b$ et $s$, où $1 \le b \le 13$ est le nombre de banques de mémoire et $1 \le s \le 13$ le nombre de variables pouvant être stockées dans chaque banque. La deuxième contient un programme non vide comportant au plus 1 000 éléments séparés par des espaces (chaque Rn, Vi et E compte pour un élément).

Vous pouvez supposer que :

• Dans une répétition Rn, le nombre de répétitions vérifie $1 \le n \le 10^6$.

• Dans une opération de boucle Rn <program> E, le corps <program> n’est pas vide.

• Dans une référence à une variable Vi, l’indice vérifie $1 \le i \le \min(b \cdot s, 13)$.

• Le nombre total de références à des variables effectuées pendant une exécution du programme est d’au plus $10^{12}$.

Sortie

Affichez le nombre minimal d’instructions à exécuter pour terminer le programme.

Exemples

Entrée 1

1 2
V1 V2 V1 V1 V2

Sortie 1

5

Entrée 2

2 1
V1 V2 V1 V1 V2

Sortie 2

6

Entrée 3

1 2
R10 V1 V2 V1 E

Sortie 3

30

Entrée 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Sortie 4

17