Термін «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$ (якщо він іще не має значення $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