Thuật ngữ “kiến trúc Harvard” chỉ máy tính có các bộ nhớ tách biệt về mặt vật lý cho lệnh và dữ liệu. Thuật ngữ này bắt nguồn từ máy tính Harvard Mark I, được IBM bàn giao năm 1944, sử dụng băng giấy cho lệnh và rơ-le cho dữ liệu.

Một số vi điều khiển hiện đại sử dụng kiến trúc Harvard — nhưng không dùng băng giấy và rơ-le! Bộ nhớ dữ liệu được tổ chức thành các bank, mỗi bank chứa cùng số lượng mục dữ liệu. Mỗi lệnh tham chiếu dữ liệu có một độ lệch byte $f$ trong bank và một bit $a$ dùng để chọn bank được tham chiếu. Nếu $a$ bằng $0$ thì tham chiếu bank $0$. Nếu $a$ bằng $1$ thì giá trị trong thanh ghi chọn bank (BSR) xác định bank được sử dụng. Giả sử mọi lệnh đều mất cùng thời gian thực hiện và có một lệnh có thể đặt giá trị của BSR.

Ảnh từ Wikimedia Commons

Ví dụ, giả sử có 4 bank, mỗi bank có 8 byte. Để truy cập vị trí $5$, có thể dùng một lệnh với $a = 0$ và $f = 5$, hoặc dùng một lệnh đặt BSR thành $0$ rồi dùng một lệnh với $a = 1$ và $f = 5$. Cách thứ nhất nhanh hơn vì không cần đặt BSR.

Bây giờ giả sử, với cùng bộ nhớ đó, vị trí cần truy cập là $20$. Chỉ có một cách thực hiện được: chạy một lệnh đặt BSR thành $2$ (trừ khi BSR đã có giá trị $2$), rồi dùng một lệnh với $a = 1$ và $f = 4$.

Chương trình là một dãy các thao tác. Mỗi thao tác là một trong hai loại:

• tham chiếu biến, viết là Vi, trong đó $i$ là số nguyên dương, hoặc

• lặp, viết là Rn <program> E, trong đó $n$ là số nguyên dương và <program> là một chương trình bất kỳ. Thao tác này tương đương với $n$ lần xuất hiện liên tiếp của <program>.

Nhiệm vụ của bạn là xác định thời gian chạy nhỏ nhất của các chương trình. Cụ thể, cho số lượng và kích thước các bank bộ nhớ cùng một chương trình cần chạy, hãy tìm số lệnh nhỏ nhất (tham chiếu vị trí bộ nhớ và có thể đặt BSR) cần thực hiện để chạy chương trình. Bạn phải xác định một cách ánh xạ biến vào các bank bộ nhớ sao cho thời gian thực hiện nhỏ nhất, rồi báo cáo thời gian đó, tức là số lần tham chiếu bộ nhớ và đặt thanh ghi BSR cần thiết. Giá trị ban đầu của BSR không được xác định và chỉ thay đổi khi một lệnh đặt giá trị của nó một cách tường minh.

Dữ liệu vào

Dữ liệu vào gồm một bộ kiểm thử có hai dòng. Dòng đầu chứa hai số nguyên $b$ và $s$, trong đó $1 \le b \le 13$ là số bank bộ nhớ và $1 \le s \le 13$ là số biến có thể lưu trong mỗi bank. Dòng thứ hai chứa một chương trình không rỗng với nhiều nhất 1 000 phần tử ngăn cách bởi dấu cách (mỗi Rn, Vi và E tính là một phần tử).

Bạn có thể giả sử những điều sau:

• Trong phép lặp Rn, số lần lặp thỏa mãn $1 \le n \le 10^6$.

• Trong thao tác vòng lặp Rn <program> E, thân vòng lặp <program> không rỗng.

• Trong tham chiếu biến Vi, chỉ số biến thỏa mãn $1 \le i \le \min(b \cdot s, 13)$.

• Tổng số lần tham chiếu biến được thực hiện khi chạy chương trình không quá $10^{12}$.

Dữ liệu ra

In ra số lệnh nhỏ nhất cần thực hiện để hoàn thành chương trình.

Ví dụ

Dữ liệu vào 1

1 2
V1 V2 V1 V1 V2

Dữ liệu ra 1

5

Dữ liệu vào 2

2 1
V1 V2 V1 V1 V2

Dữ liệu ra 2

6

Dữ liệu vào 3

1 2
R10 V1 V2 V1 E

Dữ liệu ra 3

30

Dữ liệu vào 4

4 1
V1 R2 V2 V4 R2 V1 E V3 E

Dữ liệu ra 4

17