THỰC HÀNH

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ố lần xuất hiện các cặp ngọc (a_i, b_i), tức là phải có ngọc loại a_i đi trước loại b_i (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.

Input:

• 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ị.

Output:

Một số nguyên là giá trị chuỗi ngọc.

Example:

Input:
7 3
abacaba
ab
ac
bb
Output:
7