Bessie đã chơi trò chơi đối kháng nổi tiếng Moortal Cowmbat từ lâu. Tuy nhiên, gần đây các nhà phát triển trò chơi đã tung ra một bản cập nhật buộc Bessie phải thay đổi phong cách chơi của mình.

Trò chơi sử dụng \(M\) nút được gắn nhãn bằng \(M\) chữ cái thường đầu tiên (\(1 \leq M \leq 26\)). Chuỗi chiêu thức yêu thích của Bessie trong trò chơi là một xâu \(S\) độ dài \(N\) biểu thị các lần nhấn nút (\(1 \leq N \leq 10^5\)). Tuy nhiên, do bản cập nhật gần nhất, giờ đây mọi chuỗi chiêu thức phải được tạo thành từ một loạt "đợt nhấn", trong đó một đợt nhấn được định nghĩa là một dãy gồm cùng một nút được nhấn liên tiếp ít nhất \(K\) lần (\(1 \leq K \leq N\)). Bessie muốn sửa chuỗi chiêu thức yêu thích để tạo ra một chuỗi mới có cùng độ dài \(N\), nhưng được tạo thành từ các đợt nhấn nút nhằm đáp ứng sự thay đổi về luật chơi.

Bessie mất \(a_{ij}\) ngày để luyện cách nhấn nút \(j\) thay cho nút \(i\) tại bất kỳ vị trí cụ thể nào trong chuỗi chiêu thức của mình (tức là chi phí để đổi một chữ cái cụ thể trong \(S\) từ \(i\) thành \(j\) là \(a_{ij}\)). Lưu ý rằng việc chuyển từ nút \(i\) sang một nút trung gian \(k\), rồi từ nút \(k\) sang nút \(j\), có thể tốn ít thời gian hơn so với chuyển trực tiếp từ \(i\) sang \(j\) (hoặc tổng quát hơn, có thể tồn tại một chuỗi thay đổi bắt đầu bằng \(i\) và kết thúc bằng \(j\) cho tổng chi phí tốt nhất để cuối cùng chuyển nút \(i\) thành nút \(j\)).

Hãy giúp Bessie xác định số ngày ít nhất có thể để tạo ra một chuỗi chiêu thức đáp ứng các yêu cầu mới.

Phân nhóm

• Các test 2–4 thỏa mãn \(N \leq 1000\), \(K \leq 50\).
• Các test 5–8 thỏa mãn \(N \leq 30{,}000\), \(K \leq 50\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Dòng thứ hai chứa \(S\), và \(M\) dòng cuối chứa một ma trận \(M\times M\) các giá trị \(a_{ij}\), trong đó \(a_{ij}\) là một số nguyên thuộc phạm vi \(0 \ldots 1000\) và \(a_{ii}=0\) với mọi \(i\).

Dữ liệu ra

In một số duy nhất, biểu thị số ngày tối thiểu Bessie cần để đổi chuỗi chiêu thức thành một chuỗi thỏa mãn các yêu cầu mới.

Ví dụ

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

5

Nguồn

USACO 2019 December Contest, Gold - Moortal Cowmbat: https://usaco.org/index.php?page=viewproblem2&cpid=971

Tác giả: Eric Wei.