Гарвард
Термин "Гарвардская архитектура" применима к компьютеру с физически разделенной памятью для инструкций и данных. Термин происходит от имени компьютера 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.
Выходные данные
Выведите одно число — минимальное число инструкций, необходимое для выполнения программы.