Bessie chơi game đối kháng phổ biến Moortal Cowmbat đã lâu, nhưng bản cập nhật mới buộc đổi lối chơi.

Có $M$ nút, các chữ thường đầu tiên $M$ ($1 \leq M \leq 26$). Combo yêu thích là chuỗi $S$ dài $N$ ($1 \leq N \leq 10^5$). Nay mọi combo phải gồm các «đoạn liên tiếp»: cùng nút được nhấn ít nhất $K$ lần liền ($1 \leq K \leq N$). Cô muốn sửa combo vẫn dài $N$ và gồm đoạn hợp lệ.

Luyện nhấn $j$ thay $i$ tại vị trí cụ thể cần $a_{ij}$ ngày, chi phí đổi đúng một ký tự cụ thể trong $S$ từ $i$ tới $j$. Đổi từ $i$ qua nút trung gian $k$ rồi tới $j$ có thể nhanh hơn trực tiếp. Tổng quát chuỗi thay đổi từ $i$ tới $j$ có thể cho tổng chi phí tốt nhất.

Tìm số ngày ít nhất để tạo combo đúng yêu cầu.

Dữ liệu vào

Dòng đầu chứa $N$, $M$, $K$, dòng hai $S$, cuối $M$ dòng là ma trận $M\times M$ số nguyên $a_{ij}$ trong $0 \ldots 1000$, với $a_{ii} = 0$ cho mọi $i$.

Dữ liệu ra

In một số, số ngày ít nhất để đổi combo thỏa yêu cầu.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

5

Ghi chú

Tối ưu là a sang b, d sang e, sau đó cả hai e sang c. Mất $1+4+0+0=5$ ngày và được bbccc.

Nhiệm vụ con

• Bộ 2–4: $N\le 1000, K\le 50.$
• Bộ 5–8: $N\le 30,000, K\le 50.$

Tác giả bài toán: Eric Wei