Гарвард
Термін "Гарвардська архітектура" можна застосовувати до комп'ютера з фізично розділеною пам'яттю для інструкцій та даних. Термін походить від імені комп'ютера Harvard Mark I, створеного у 1944 році. У ньому для інструкцій використовувалась паперова стрічка, а для даних — реле.
Деякі сучасні мікроконтролери використовують "Гарвардську архітектуру", але не паперові стрічки та реле! Дані лежать у банках, кожен з яких містить однакове число комірок. Кожна інструкція звернення до даних має байт-зміщенння f у межах банку та біт a, який використовується для визначення номера банку. Якщо a дорівнює 0, то звернення відбувається до банку під номером 0. Якщо a дорівнює 1, то номер банку зберігається у спеціальному регістрі вибору банку (РВБ).
Наприклад, нехай у нас є 4 банки з 8 комірками кажен. Звернутись до комірки під номером 5 можна двома способами: однією інструкцією з a = 0 та f = 5 або двома інструкціями, встановивши значення РВБ рівним 0 і потім використавши інструкцію з a = 1 та f = 5. Очевидно, що перший спосіб швидший, бо не потрібно присвоювати значення РВБ. Тепер припустимо, що потрібно звернутись до комірки 20 у тій же пам'яті. Тепер можна застосувати лише один спосіб: виконати інструкцію, встановивши значення РВБ 2 (якщо у ньому вже не зберігається потрібне значення), а потім інструкцію з a = 1 та f = 4. Програма являє собою послідовність операцій. Кожна операція це:
звернення до змінної, записується як V_i, де i — додатне ціле число;
повторення, записується як R_n < program > E, де n — додатне ціле число, а < program > — довільна програма, ця операція еквівалентна виконанню програми n разів.
Задача полягає у визначенні мінімального часу виконання програми. А саме, знаючи кількість та розмір банків, а також маючи програму, потрібно визначити мінімальну кількість інструкцій 1 (звернення до комірок та, можливо, встановлення значення РВБ) необхідних для виконання програми. Для цього вам потрібно асоціювати змінні з комірками пам'яті і серед усіх відображень визначити те, яке мінімізує число інструкцій. Потрібно вивести саме це число. Зверніть увагу, що значення РВБ до першого присвоєння не визначено.
Вхідні дані
Вхідні дані містять один тест, який складається з двох рядків. У першому b та s — кількість банків та кількість змінних, які можна зберігати у банку. Другй рядок містить непорожню програму з не більш ніж 1000 елементів (кожен з R_n, V_i та E вважається за один елемент).
Можно припускати, що:
у повторенні R_n, n задовольняє умові 1 ≤ n ≤ 10^6;
тіло повторення R_n < program > E < program > не порожнє;
при звертанні до змінної V_i, i задовольняє умову 1 ≤ i ≤ min(b*s, 13);
загальне число звернень до змінних у програмі не перевищує 10^12.
Вихідні дані
Виведіть одне число — мінімальне число інструкцій, необхідних для виконання програми.