Harvard

The term "Harvard architecture" describes a computer that keeps its instructions and its data in physically separate memories. The name comes from the Harvard Mark I, delivered by IBM in 1944, which stored instructions on paper tape and data in relays.

Some modern microcontrollers also use a Harvard architecture, though without paper tape or relays. Data memory is divided into banks, and every bank holds the same number of data items. Each data-referencing instruction carries a byte offset $f$ into a bank and a bit $a$ that selects which bank is used.

• If $a = 0$, bank $0$ is referenced.
• If $a = 1$, the bank named by the bank select register (BSR) is referenced.

Assume every instruction takes the same amount of time, and that a separate instruction can load a value into the BSR.

For example, suppose there are $4$ banks of $8$ bytes each. To reach location $5$ you can either issue one instruction with $a = 0$ and $f = 5$, or first set the BSR to $0$ and then issue an instruction with $a = 1$ and $f = 5$. The first way is faster because it needs no BSR update.

Now suppose, with the same memory, you must reach location $20$. Only one way works: set the BSR to $2$ (unless it already holds $2$), then issue an instruction with $a = 1$ and $f = 4$.

A program is a sequence of operations. Each operation is one of:

• a variable reference, written $V_i$, where $i$ is a positive integer, or
• a repetition, written $R_n\ \langle P\rangle\ E$, where $n$ is a positive integer and $P$ is any program; it is equivalent to running $P$ exactly $n$ times in a row.

You may freely choose which bank each variable is mapped to, as long as no bank holds more than its allowed number of variables. Given the number and size of the banks and a program to run, choose the mapping that minimizes the running time, and report that time: the total number of instructions executed (memory references plus BSR loads). The BSR starts undefined and changes only when an instruction explicitly loads it.

The input is a single test case on two lines. The first line has two integers $b$ and $s$ ($1 \le b \le 13$, $1 \le s \le 13$): $b$ is the number of memory banks and $s$ is the number of variables that fit in one bank. The second line is a non-empty program of at most $1000$ space-separated elements (each $R_n$, $V_i$, and $E$ counts as one element).

You may assume:

• In a repetition $R_n$, $1 \le n \le 10^6$.
• In a repetition $R_n\ \langle P\rangle\ E$, the body $P$ is non-empty.
• In a variable reference $V_i$, $1 \le i \le \min(b \cdot s, 13)$.
• The total number of variable references made by one execution of the program is at most $10^{12}$.

Print the minimum number of instructions needed to run the program.