Термин «Harvard-архитектура» применяется к компьютерам с физически раздельной памятью для команд и данных. Он возник благодаря компьютеру Harvard Mark I, поставленному IBM в 1944 году, который использовал бумажную ленту для команд и реле для данных.

Некоторые современные микроконтроллеры используют Harvard-архитектуру, но не бумажную ленту и реле! Память данных организована в банки, каждый из которых содержит одинаковое число элементов данных. У каждой команды обращения к данным есть байтовое смещение $f$ внутри банка и бит $a$ для выбора банка. Если $a$ равен $0$, используется банк $0$. Если $a$ равен $1$, нужный банк определяется значением регистра выбора банка (BSR). Считайте, что все команды выполняются за одинаковое время и существует команда, устанавливающая значение BSR.

Изображение из Wikimedia Commons

Например, пусть есть 4 банка по 8 байт. Для доступа к позиции $5$ можно использовать одну команду с $a = 0$ и $f = 5$ либо одной командой установить BSR в $0$, а затем использовать команду с $a = 1$ и $f = 5$. Первый способ быстрее, поскольку не требует установки BSR.

Теперь предположим, что в той же памяти требуется доступ к позиции $20$. Здесь работает только один способ: выполнить команду установки BSR в $2$ (если только BSR уже не имеет значение $2$), а затем использовать команду с $a = 1$ и $f = 4$.

Программа — это последовательность операций. Каждая операция представляет собой либо

• обращение к переменной, записываемое как Vi, где $i$ — положительное целое число, либо

• повторение, записываемое как Rn <program> E, где $n$ — положительное целое число, а <program> — произвольная программа. Эта операция эквивалентна $n$ последовательным вхождениям <program>.

Ваша задача — определить минимальное время выполнения программ. В частности, по заданным числу и размеру банков памяти и программе найдите минимальное число команд (обращающихся к позициям памяти и, возможно, устанавливающих BSR), которые надо выполнить для запуска программы. Для этого нужно найти распределение переменных по банкам, дающее наименьшее время выполнения, и сообщить это время — число необходимых обращений к памяти и установок регистра BSR. Начальное значение BSR не определено и меняется только при явной установке командой.

Входные данные

Входные данные содержат один тестовый случай из двух строк. Первая строка содержит два целых числа $b$ и $s$, где $1 \le b \le 13$ — число банков памяти, а $1 \le s \le 13$ — число переменных, которые можно хранить в каждом банке. Вторая строка содержит непустую программу, состоящую не более чем из 1 000 элементов, разделённых пробелами (каждое Rn, Vi и E считается одним элементом).

Можно считать, что выполнены следующие условия:

• В повторении Rn число повторений удовлетворяет $1 \le n \le 10^6$.

• В операции цикла Rn <program> E тело цикла <program> непусто.

• В обращении к переменной Vi индекс переменной удовлетворяет $1 \le i \le \min(b \cdot s, 13)$.

• Общее число обращений к переменным за одно выполнение программы не превышает $10^{12}$.

Выходные данные

Выведите минимальное число команд, которые необходимо выполнить для завершения программы.

Примеры

Входные данные 1

1 2
V1 V2 V1 V1 V2

Выходные данные 1

5

Входные данные 2

2 1
V1 V2 V1 V1 V2

Выходные данные 2

6

Входные данные 3

1 2
R10 V1 V2 V1 E

Выходные данные 3

30

Входные данные 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Выходные данные 4

17