Bessie đã chơi trò chơi đối kháng Moortal Cowmbat trong một thời gian dài. Tuy nhiên gần đây, những nhà phát triển trò chơi đã thực hiện một cập nhật mới khiến cho Bessie phải thay đổi phong cách chơi của bạn ấy.

Trò chơi sử dụng ~M~ nút bấm là ~M~ chữ cái in thường đầu tiên trong bảng chữ cái Latin. Combo yêu thích của Bessie được biểu diễn dưới dạng một xâu các nút bấm ~S~, độ dài ~N~. Tuy nhiên theo như cập nhật mới nhất của trò chơi, nếu mỗi nút bấm được thực hiện, nó phải nằm trong một nhóm chứa ít nhất ~K~ nút bấm liên tiếp giống nó. Bessie muốn thay đổi combo của bạn ấy sao cho phù hợp với yêu cầu mới của trò chơi.

Bessie mất ~a_{ij}~ ngày để luyện tập khả năng bấm nút từ kí tự ~i~ sang ~j~ tại một vị trí bấm nút ~i~ trong xâu ~S~. Hãy giúp Bessie tìm ra số ngày ít nhất để bạn ấy có thể chơi trò chơi yêu thích của mình.

Input

• Dòng đầu tiên ghi các số nguyên dương ~N~, ~M~, ~K~ ~(1 \le K \le N \le 100000, 1 \le M \le 26)~.

• Dòng thứ hai chứa xâu ~S~ ban đầu.

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~M~ số ~a_{i1}...a_{iM}~ thể hiện số ngày thay đổi kí tự từ ~i~ sang kí tự ~j~. ~(0 \le a_{ij} \le 1000)~.

Output

• In ra số ngày biến đổi ít nhất để xâu ~S~ hợp lệ.

Sample Input

5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0

Sample Output

5

Note

• Giải thích: thay đổi ~a~ thành ~b~, ~d~ thành ~e~, sau đó cả 2 kí tự ~e~ thành ~c~.

• Các tests 2-4 thoả mãn ~N \le 1000, K \le 50~.

• Các tests 5-8 thoả mãn ~N \le 30000, K \le 50~.