#291. Keyboarding (KEYBOARD)

Cho một "bàn phím ảo" trên TV có kích thước hàng và cột. Thông qua 5 phím điều khiển: "Lên, Xuống, Trái, Phải, Chọn", bạn có thể di chuyển con trỏ trên màn hình TV để in văn bản. Ban đầu, con trỏ nằm ở góc trên bên trái của bàn phím.

Mỗi lần nhấn phím điều hướng, con trỏ sẽ luôn nhảy đến ký tự tiếp theo khác với ký tự ở vị trí hiện tại theo hướng đó; nếu không tồn tại ký tự nào như vậy thì con trỏ không di chuyển. Mỗi lần nhấn phím "Chọn", ký tự tại vị trí con trỏ sẽ được in ra.

Yêu cầu: Tính số lần nhấn phím ít nhất để in ra văn bản cho trước (cần in thêm một dấu xuống dòng ở cuối).

Dữ liệu:

• Dòng đầu tiên nhập hai số nguyên .
• Tiếp theo là mô tả bàn phím kích thước , bao gồm các chữ cái in hoa, chữ số, dấu gạch ngang và dấu sao (dấu sao * đại diện cho phím Enter để xuống dòng).
• Dòng cuối cùng là chuỗi văn bản cần in, độ dài của không vượt quá .

Kết quả:

• Xuất ra số lần nhấn phím ít nhất để in văn bản (bao gồm cả dấu xuống dòng ở cuối). Dữ liệu đảm bảo luôn có nghiệm.

Ví dụ:

Dữ liệu:

2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ

Kết quả:

19

Dữ liệu:

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

Kết quả:

160

Dữ liệu:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB

Kết quả:

7

Giới hạn: , độ dài của không vượt quá .