CHUỖI NGỌC

Dọc theo con đường tơ lụa những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của phương đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên (1 ≤ n ≤ 100 000). Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (ai, bi), tức là phải có ngọc loại ai đi trước loại bi (i = 1÷ k, 1 ≤ k ≤ 676).

Nếu giá trị chuỗi ngọc đủ lớn, lãnh chúa sẽ mua toàn bộ chuỗi ngọc.

Yêu cầu: Cho biết n và xâu S thể hiện các loại ngọc trong chuỗi, cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc.

Dữ liệu: Vào từ file văn bản GEMS.INP:

+ Dòng đầu tiên chứa 2 số nguyên n và k,

+ Dòng thứ 2 chứa xâu S,

+ Mỗi dòng trong k dòng sau chứa xâu 2 ký tự xác định cặp có giá trị.

Kết quả: Đưa ra file văn bản GEMS.OUT một số nguyên – giá trị chuỗi ngọc.

Ví dụ:

GEMS.INP	GEMS.OUT
7 3 abacaba ab ac bb	7

SOLUTION