\includegraphics{https://static.e-olymp.com/content/d0/d0258f2cc3a4da1a66073ace138adede1dd185d4.jpg} The term "Harvard architecture" applies to a computer that has physically separate memories for instructions and data. The term originated with the Harvard Mark I computer, delivered by IBM in 1944, which used paper tape for instructions and relays for data. Some modern microcontrollers use the Harvard architecture -- but not paper tape and relays! Data memory is organized in banks, each containing the same number of data items. Each data-referencing instruction has a byte offset \textbf{f} to a bank, and a bit \textbf{a} that is used to select the bank to be referenced. If \textbf{a} is \textbf{0}, then bank \textbf{0} is referenced. If \textbf{a} is \textbf{1}, then the value in a \textit{bank select register} (\textbf{BSR}) identifies the bank to be used. Assume each instruction takes the same time to execute, and there is an instruction that can set the \textbf{BSR}’s value. For example, suppose there are \textbf{4} banks of \textbf{8} bytes each. To access location \textbf{5}, either use a single instruction with \textbf{a = 0} and \textbf{f = 5}, or set the \textbf{BSR} to \textbf{0} in one instruction and then use an instruction with \textbf{a = 1} and \textbf{f = 5}. The first approach is faster since it does not require setting the \textbf{BSR}. Now suppose (with the same memory) the location to access is \textbf{20}. Only one approach will work here: execute an instruction that sets the \textbf{BSR} to \textbf{2} (unless the \textbf{BSR} already has the value \textbf{2}) and then use an instruction with \textbf{a = 1} and \textbf{f = 4}. A \textit{program} is a sequence of operations. Each operation is either \begin{itemize} \item a variable reference, written as \textbf{V_i}, where \textbf{i} is a positive integer, or \item a repetition, written as \textbf{R_n} <\textbf{program}> \textbf{E}, where \textbf{n} is a positive integer and <\textbf{program}> is an arbitrary program. This operation is equivalent to \textbf{n} sequential occurrences of <\textbf{program}>. \end{itemize} Your problem is to determine the minimum running time of programs. In particular, given the number and size of the memory banks and a program to be executed, find the minimum number of instructions (which reference memory location and possibly set the \textbf{BSR}) that must be executed to run the program. To do this you must identify a mapping of variables to memory banks that yields the smallest execution time, and report that execution time -- that is, the number of memory references and \textbf{BSR} register settings required. The \textbf{BSR}’s value is initially undefined, and changes only when an instruction explicitly sets its value. \InputFile The input consists of a single test case. A test case consists of two lines. The first line contains two integers \textbf{b} and \textbf{s}, where \textbf{1} ≤ \textbf{b} ≤ \textbf{13} is the number of memory banks and \textbf{1} ≤ \textbf{s} ≤ \textbf{13} is the number of variables that can be stored in each memory bank. The second line contains a non-empty program with at most \textbf{1000} space-separated elements (each \textbf{R_n},\textbf{V_i}, and \textbf{E} counts as one element). You may assume the following: \begin{itemize} \item In a repetition \textbf{R_n}, the number of repetitions satisfies \textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}. \item In a loop operation \textbf{R_n} <\textbf{program}> \textbf{E}, the loop body <\textbf{program}> is not empty. \item In a variable reference \textbf{V_i}, the variable index satisfies \textbf{1} ≤ \textbf{i} ≤ \textbf{min(b·s, 13)}. \item The total number of variable references performed by an execution of the program is at most \textbf{10^12}. \end{itemize} \OutputFile Display the minimum number of instructions that must be executed to complete the program.