“哈佛架构”一词适用于具有物理上分离的指令存储器和数据存储器的计算机。该术语起源于 1944 年由 IBM 交付的哈佛马克一号（Harvard Mark I）计算机，它使用纸带存储指令，使用继电器存储数据。

Picture from Wikimedia Commons

一些现代微控制器使用哈佛架构——但不再使用纸带和继电器！数据存储器被组织成若干个存储体（bank），每个存储体包含相同数量的数据项。每条数据引用指令都有一个指向存储体的字节偏移量 $f$ 和一个用于选择所引用存储体的位 $a$。如果 $a$ 为 0，则引用存储体 0。如果 $a$ 为 1，则存储体选择寄存器（BSR）中的值标识要使用的存储体。假设每条指令执行时间相同，并且存在一条可以设置 BSR 值的指令。

例如，假设有 4 个存储体，每个存储体 8 字节。要访问位置 5，可以使用一条 $a=0$ 且 $f=5$ 的指令，或者先用一条指令将 BSR 设置为 0，然后使用一条 $a=1$ 且 $f=5$ 的指令。第一种方法更快，因为它不需要设置 BSR。

现在假设（使用相同的内存）要访问的位置是 20。这里只有一种方法可行：执行一条将 BSR 设置为 2 的指令（除非 BSR 已经具有值 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