题目描述

“哈佛结构”是指一台拥有多个分散内存用于记录指令与数据的计算机。这个术语起源于“哈佛马克 $1$ 号”计算机。它由 IBM 于 $1944$ 年制造，用纸带记录指令，用继电器来储存数据。

一些最新的单片机使用了“哈佛结构”（当然没有用纸带和继电器）。数据是由“内存库”来组织，每个“内存库”拥有相同数量的数据。每一个访问数据的指令都由 $2$ 个数控制。一个数 $a$（非 $0$ 即 $1$）。如果 $a$ 为 $0$，那么访问的是 $0$ 号“内存库”。如果 $a$ 为 $1$ 则访问 BSR（bank select register “内存库”选择寄存器）中选择的“内存库”。另一个数 $f$ 表示访问该“内存库”的第 $f$ 个变量。我们假设每一个指令花费相同的时间运行。另外还有一个可以设定 BSR 值的命令。

举例来说，假设有 $4$ 个“内存库”，每个“内存库”有 $8$ 个字节。为了访问位置 $5$（$0$ 号“内存库”第 $5$ 个变量），我们有两种方法。第一种，使用指令 $a=0,f=5$。第二种，先将 BSR 的值设为 $0$，然后使用指令 $a=1,f=5$。第一种方法更快，因为它不需要花费时间设置BSR。

现在假设（还是刚才的“内存库”）我们要访问位置 $20$（$2$ 号“内存库”第 $4$ 个变量）。现在只有 $1$ 种方法能够访问。将 BSR 的值设为 $2$（除非 BSR 原来就是 $2$），然后用指令 $a=1,f=4$。

一个程序是一个操作的序列，每个操作是：

• 一个变量访问操作，写作 $v_i$，$i$ 是一个正整数。

• 一个循环操作，写作 Rn <program> E，$n$ 是一个正整数，<program> 是一个任意的程序。这个操作等价于依次执行 $n$ 遍 <program>。

你的工作是决定一个程序最小的运行时间。更确切的说，给出“内存库”的个数和大小，需要执行的程序，输出为了执行这个程序最小的指令数（包括数据访问指令和设定 BSR 的指令）。为了完成这个，你必须设定一个变量到“内存库”的映射，使得这个程序运行时间最短，并且输出这个时间（也就是程序运行的指令数）。开始的时候 BSR 的值为 undefined，直到一条命令显式的设定了它的值。

输入格式

每组输入包含一个测试数据，共两行。

第一行两个整数 $b$ 和 $s$，$b$ 代表“内存库”的个数，$s$ 代表每个“内存库”的大小（即能储存的变量数）。

第二行是一个非空程序，最多有 $10^3$ 个元素（每个 $R_n,v_i,E$ 都算 $1$ 个元素）。

保证：

• 在循环 $R_n$ 中，循环次数 $1\leq n\leq 10^6$。

• 在循环 Rn <program> E 中，<program> 非空。

• 在数据访问 $v_i$ 中，$1\leq i\leq \min(b\times s,13)$。

• 程序访问变量的次数不超过 $10^{12}$ 次。

输出格式

输出运行该程序最少需要的指令数。

1 2
V1 V2 V1 V1 V2

5

数据规模与约定

对于 $100\%$ 的数据，$1\leq s,b\leq 13$。