「Harvard 架構」是指指令和資料使用實體分離記憶體的電腦。這個名稱源自 IBM 於 1944 年交付的 Harvard Mark I 電腦，它以紙帶儲存指令，以繼電器儲存資料。

一些現代微控制器採用 Harvard 架構，但不使用紙帶和繼電器！資料記憶體被劃分為多個儲存區，每個儲存區包含相同數量的資料項目。每條存取資料的指令都有儲存區內的位元組偏移量 $f$，以及用來選擇儲存區的一個位元 $a$。若 $a$ 為 $0$，則存取儲存區 $0$。若 $a$ 為 $1$，則由儲存區選擇暫存器（BSR）的值指定要使用的儲存區。假設每條指令執行所需時間相同，且有一條可以設定 BSR 值的指令。

圖片來自 Wikimedia Commons

例如，假設有 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