Termin „architektura Harvard” odnosi się do komputera mającego fizycznie oddzielne pamięci na instrukcje i dane. Nazwa pochodzi od komputera Harvard Mark I, dostarczonego przez IBM w 1944 roku, który używał taśmy papierowej do instrukcji i przekaźników do danych.

Niektóre współczesne mikrokontrolery korzystają z architektury Harvard — lecz nie z taśmy papierowej i przekaźników! Pamięć danych jest podzielona na banki, zawierające po tyle samo elementów danych. Każda instrukcja odwołująca się do danych ma przesunięcie bajtowe $f$ wewnątrz banku oraz bit $a$ wybierający bank, do którego następuje odwołanie. Jeśli $a$ wynosi $0$, używany jest bank $0$. Jeśli $a$ wynosi $1$, wartość rejestru wyboru banku (BSR) wskazuje używany bank. Załóż, że wykonanie każdej instrukcji trwa tyle samo i że istnieje instrukcja ustawiająca wartość BSR.

Zdjęcie z Wikimedia Commons

Na przykład załóżmy, że istnieją 4 banki po 8 bajtów każdy. Aby uzyskać dostęp do pozycji $5$, można użyć pojedynczej instrukcji z $a = 0$ i $f = 5$ albo jedną instrukcją ustawić BSR na $0$, a następnie użyć instrukcji z $a = 1$ i $f = 5$. Pierwszy sposób jest szybszy, ponieważ nie wymaga ustawiania BSR.

Teraz załóżmy, że w tej samej pamięci trzeba uzyskać dostęp do pozycji $20$. Zadziała tylko jeden sposób: wykonać instrukcję ustawiającą BSR na $2$ (chyba że BSR ma już wartość $2$), a następnie użyć instrukcji z $a = 1$ i $f = 4$.

Program jest ciągiem operacji. Każda operacja jest albo

• odwołaniem do zmiennej, zapisanym jako Vi, gdzie $i$ jest dodatnią liczbą całkowitą, albo

• powtórzeniem, zapisanym jako Rn <program> E, gdzie $n$ jest dodatnią liczbą całkowitą, a <program> jest dowolnym programem. Operacja ta odpowiada $n$ kolejnym wystąpieniom <program>.

Twoim zadaniem jest wyznaczyć minimalny czas wykonania programów. Dokładniej, mając liczbę i rozmiar banków pamięci oraz program do wykonania, znajdź minimalną liczbę instrukcji (odwołujących się do pozycji pamięci i ewentualnie ustawiających BSR), które trzeba wykonać, aby zrealizować program. W tym celu musisz znaleźć przypisanie zmiennych do banków dające najmniejszy czas wykonania i podać ten czas, czyli liczbę wymaganych odwołań do pamięci oraz ustawień rejestru BSR. Początkowa wartość BSR jest niezdefiniowana i zmienia się tylko wtedy, gdy instrukcja jawnie ją ustawi.

Wejście

Wejście zawiera jeden przypadek testowy złożony z dwóch wierszy. Pierwszy zawiera dwie liczby całkowite $b$ i $s$, gdzie $1 \le b \le 13$ jest liczbą banków pamięci, a $1 \le s \le 13$ liczbą zmiennych, które można przechowywać w każdym banku. Drugi wiersz zawiera niepusty program z co najwyżej 1 000 elementów oddzielonych spacjami (każde Rn, Vi i E liczy się jako jeden element).

Możesz przyjąć następujące założenia:

• W powtórzeniu Rn liczba powtórzeń spełnia $1 \le n \le 10^6$.

• W operacji pętli Rn <program> E ciało pętli <program> nie jest puste.

• W odwołaniu do zmiennej Vi indeks zmiennej spełnia $1 \le i \le \min(b \cdot s, 13)$.

• Łączna liczba odwołań do zmiennych podczas wykonania programu nie przekracza $10^{12}$.

Wyjście

Wypisz minimalną liczbę instrukcji, które trzeba wykonać, aby zakończyć program.

Przykład

Wejście 1

1 2
V1 V2 V1 V1 V2

Wyjście 1

5

Wejście 2

2 1
V1 V2 V1 V1 V2

Wyjście 2

6

Wejście 3

1 2
R10 V1 V2 V1 E

Wyjście 3

30

Wejście 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Wyjście 4

17