Giải bài trực tuyến

Các phân tử trong tế bào sinh học được cấu tạo từ 4 loại nuclêôtit cơ bản ký hiệu bởi các chữ cái A, X, T, G. Mỗi gen di truyền được cấu tạo thành bởi một chuỗi các nuclêôtit với độ dài được tính bằng số lượng nuclêôtit. Ví dụ, AXXTTGAT là một gen có độ dài 8.

Trong một chuyến đi khảo sát, Giáo sư Altein phát hiện ra một gen lạ gồm n nuclêôtit được xếp trên một vòng tròn. Ngay lập tức, Giáo sư Altein dự định tiến hành so sánh gen lạ này với một số gen mẫu đang lưu trữ nhằm tìm hiểu xem mẫu gen này có gần gũi với loại gen mẫu nào đã được biết. Trong sinh học để đo độ khác biệt giữa hai mẫu gen người ta thường tính khoảng cách Hamming giữa chúng. Khoảng cách Hamming giữa hai gen cùng độ dài được định nghĩa là số lượng vị trí mà tại đó hai gen chứa các nuclêôtit khác nhau. Ví dụ, hai gen AGGTT và TGATT có khoảng cách Hamming bằng 2 do 2 nuclêôtit ở các vị trí 1 và 3 của chúng là khác nhau. Do các gen mẫu được sử dụng đều có độ dài m (m ≤ n) và có cấu trúc thẳng, trong khi gen lạ lại có độ dài n và có cấu trúc vòng nên Giáo sư Altein đã định nghĩa khoảng cách Hamming giữa một gen mẫu và gen lạ là số nhỏ nhất trong số các khoảng cách Hamming giữa gen mẫu và những đoạn gen gồm m nuclêôtit liên tiếp theo chiều kim đồng hồ trong gen lạ.

Yêu cầu: Cho k gen mẫu, hãy xác định gen mẫu với khoảng cách Hamming đến gen lạ là nhỏ nhất và đưa ra khoảng cách tìm được.

Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.

Input

• Dòng thứ nhất chứa ba số nguyên dương n, m, k (m ≤ n ≤ 1000; k ≤ 100).
• Dòng thứ hai chứa xâu độ dài n là dãy các nuclêôtit của gen lạ được liệt kê theo chiều kim đồng hồ bắt đầu từ một vị trí nào đó.
• Dòng thứ i trong số k dòng tiếp theo chứa xâu độ dài m biểu diễn gen mẫu thứ i.

Output

Ghi ra một số nguyên là khoảng cách Hamming nhỏ nhất tìm được.

Example

Input:
7 3 2
GTAAXXT
GAT
TTT

Output:
1