「Harvard アーキテクチャ」とは、命令とデータに物理的に別々のメモリを使うコンピュータを指します。この用語は、IBM が 1944 年に納入した Harvard Mark I コンピュータに由来します。このコンピュータは、命令に紙テープ、データにリレーを使っていました。

現代のマイクロコントローラにも Harvard アーキテクチャを使うものがありますが、紙テープとリレーは使いません！データメモリはバンクに分けられ、各バンクには同じ個数のデータ項目が入ります。各データ参照命令は、バンク内のバイトオフセット $f$ と、参照するバンクを選ぶためのビット $a$ を持ちます。$a$ が $0$ ならバンク $0$ を参照します。$a$ が $1$ なら、バンク選択レジスタ（BSR）の値が使用するバンクを指定します。各命令の実行時間は同じであり、BSR の値を設定する命令があると仮定します。

画像の出典：Wikimedia Commons

例えば、それぞれ 8 バイトのバンクが 4 個あるとします。位置 $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> は任意のプログラムです。この操作は <program> を順に $n$ 回実行することと同じです。

プログラムの最小実行時間を求めてください。具体的には、メモリバンクの個数とサイズ、および実行するプログラムが与えられるので、プログラムを実行するために必要な命令（メモリ位置を参照し、場合によって BSR を設定する命令）の最小実行回数を求めます。そのために、実行時間を最小にする変数からメモリバンクへの割り当てを見つけ、その実行時間、すなわち必要なメモリ参照回数と BSR 設定回数の合計を報告しなければなりません。BSR の初期値は未定義であり、命令が明示的に値を設定したときだけ変化します。

入力

入力は一つのテストケースからなり、2 行で与えられます。最初の行には二つの整数 $b$ と $s$ が含まれます。$1 \le b \le 13$ はメモリバンク数、$1 \le s \le 13$ は各バンクに格納できる変数の個数です。2 行目には、空白で区切られた要素を高々 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)$ を満たします。

• プログラムを 1 回実行する際の変数参照回数の合計は高々 $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