Combo chiến đấu

Cho xâu $S$ gồm $N$ ký tự (dùng $M$ chữ cái đầu). Có thể đổi ký tự $i$ thành $j$ với chi phí $a[i][j]$. Cần biến $S$ thành xâu mà mọi đoạn ký tự giống nhau liên tiếp đều có độ dài $\ge K$. Tìm chi phí tối thiểu.

Dữ liệu vào

• Dòng đầu: $N$, $M$, $K$.
• Dòng thứ hai: xâu $S$.
• $M$ dòng tiếp: ma trận chi phí $M\times M$ ($a[i][i]=0$).

Dữ liệu ra

Chi phí tối thiểu.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le M\le 26$
• $1\le K\le N$
• $0\le a[i][j]\le 1000$

Ví dụ