Một xâu độ dài có độ lặp là nếu có thể biểu diễn nó dưới dạng tổng một xâu nào đó lần. Ví dụ xâu aabaabaabaab có thể coi độ lặp là hoặc nhưng không thể có độ lặp là
Cho phép biến đổi, mỗi phép được xác định bởi ba tham số thay một ký tự bằng một ký tự với chi phí . Có thể có nhiều phép biến đổi hai ký tự giống nhau nhưng có chi phí khác nhau. Ví dụ: và phép biến đổi: . Ta có thể biến đổi xâu như sau:
Với chi phí biến đổi là: .
Yêu cầu: Hãy xác định chi phí nhỏ nhất để biến đổi xâu thành một xâu có độ lặp lớn hơn .
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên ;
Dòng thứ hai chứa xâu gồm ký tự la tinh thường;
dòng tiếp, mỗi dòng chứa hai chữ cái la tinh thường và một số nguyên xác định một phép biến đổi.
Dữ liệu ra:
Ghi ra chi phí biến đổi nhỏ nhất. Ghi ra trong trường hợp không tồn tại phép biến đổi.
