Der Begriff „Harvard-Architektur“ bezeichnet einen Computer mit physisch getrennten Speichern für Befehle und Daten. Er geht auf den Computer Harvard Mark I zurück, den IBM 1944 auslieferte und der Lochstreifen für Befehle und Relais für Daten verwendete.

Einige moderne Mikrocontroller verwenden die Harvard-Architektur, aber keine Lochstreifen und Relais! Der Datenspeicher ist in Bänke unterteilt, die jeweils gleich viele Datenelemente enthalten. Jeder Befehl mit Datenzugriff hat einen Byte-Offset $f$ innerhalb einer Bank und ein Bit $a$ zur Auswahl der anzusprechenden Bank. Ist $a$ gleich $0$, wird Bank $0$ angesprochen. Ist $a$ gleich $1$, bestimmt der Wert eines Bankauswahlregisters (BSR) die zu verwendende Bank. Nimm an, dass jeder Befehl gleich viel Ausführungszeit benötigt und dass es einen Befehl zum Setzen des BSR-Wertes gibt.

Bild von Wikimedia Commons

Angenommen, es gibt 4 Bänke mit jeweils 8 Bytes. Um auf Adresse $5$ zuzugreifen, verwendet man entweder einen einzelnen Befehl mit $a = 0$ und $f = 5$ oder setzt das BSR mit einem Befehl auf $0$ und verwendet dann einen Befehl mit $a = 1$ und $f = 5$. Die erste Methode ist schneller, da das BSR nicht gesetzt werden muss.

Angenommen, bei demselben Speicher soll nun auf Adresse $20$ zugegriffen werden. Hier funktioniert nur eine Methode: ein Befehl setzt das BSR auf $2$ (sofern es nicht bereits den Wert $2$ hat), und anschließend wird ein Befehl mit $a = 1$ und $f = 4$ verwendet.

Ein Programm ist eine Folge von Operationen. Jede Operation ist entweder

• ein Variablenzugriff, geschrieben als Vi, wobei $i$ eine positive ganze Zahl ist, oder

• eine Wiederholung, geschrieben als Rn <program> E, wobei $n$ eine positive ganze Zahl und <program> ein beliebiges Programm ist. Diese Operation entspricht $n$ aufeinanderfolgenden Vorkommen von <program>.

Deine Aufgabe ist es, die minimale Laufzeit von Programmen zu bestimmen. Insbesondere sind die Anzahl und Größe der Speicherbänke sowie ein auszuführendes Programm gegeben. Gesucht ist die minimale Anzahl auszuführender Befehle (die Speicheradressen ansprechen und gegebenenfalls das BSR setzen), um das Programm auszuführen. Dazu musst du eine Zuordnung von Variablen zu Speicherbänken finden, die die kleinste Laufzeit ergibt, und diese Laufzeit angeben, also die Anzahl erforderlicher Speicherzugriffe und BSR-Setzvorgänge. Der Anfangswert des BSR ist undefiniert und ändert sich nur, wenn ein Befehl ihn ausdrücklich setzt.

Eingabe

Die Eingabe besteht aus einem einzigen Testfall mit zwei Zeilen. Die erste enthält zwei ganze Zahlen $b$ und $s$. Dabei ist $1 \le b \le 13$ die Anzahl der Speicherbänke und $1 \le s \le 13$ die Anzahl der Variablen, die in jeder Speicherbank gespeichert werden können. Die zweite Zeile enthält ein nicht leeres Programm mit höchstens 1 000 durch Leerzeichen getrennten Elementen (jedes Rn, Vi und E zählt als ein Element).

Du darfst Folgendes annehmen:

• In einer Wiederholung Rn erfüllt die Wiederholungszahl $1 \le n \le 10^6$.

• Bei einer Schleifenoperation Rn <program> E ist der Schleifenrumpf <program> nicht leer.

• Bei einem Variablenzugriff Vi erfüllt der Variablenindex $1 \le i \le \min(b \cdot s, 13)$.

• Die Gesamtzahl der Variablenzugriffe während einer Programmausführung beträgt höchstens $10^{12}$.

Ausgabe

Gib die minimale Anzahl von Befehlen aus, die zum Abschließen des Programms ausgeführt werden müssen.

Beispiele

Eingabe 1

1 2
V1 V2 V1 V1 V2

Ausgabe 1

5

Eingabe 2

2 1
V1 V2 V1 V1 V2

Ausgabe 2

6

Eingabe 3

1 2
R10 V1 V2 V1 E

Ausgabe 3

30

Eingabe 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Ausgabe 4

17