「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