Bessie 玩流行格鬥遊戲 Moortal Cowmbat 已很久，但開發者最近的更新迫使牠改變玩法。

遊戲有 $M$ 個按鈕，以前 $M$ 個小寫字母標記（$1 \leq M \leq 26$）。牠最喜歡的連招是長度為 $N$ 的按鍵字串 $S$（$1 \leq N \leq 10^5$）。更新後每個連招必須由若干「連續段」組成，即同一按鈕連續按至少 $K$ 次（$1 \leq K \leq N$）。牠想修改最愛的連招，得到同長 $N$ 且符合規則的連續段連招。

牠訓練在連招的一個指定位置按按鈕 $j$ 而非 $i$ 需要 $a_{ij}$ 天，即把 $S$ 的某一個字母從 $i$ 改為 $j$ 的費用為 $a_{ij}$。先從 $i$ 改為中間按鈕 $k$ 再從 $k$ 改為 $j$ 可能比直接改更快；更一般地，從 $i$ 到 $j$ 的某條修改路徑可能給出最終轉換的最佳總費用。

幫助 Bessie 求出構造滿足新要求的連招最少需要的天數。

輸入格式

第一行含 $N$、$M$、$K$；第二行含 $S$；最後 $M$ 行為 $M\times M$ 矩陣 $a_{ij}$，每個值為 $0 \ldots 1000$ 的整數，所有 $i$ 滿足 $a_{ii} = 0$。

輸出格式

輸出一個數，表示牠把連招改為符合新要求的連招所需最少天數。

範例

輸入格式 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

輸出格式 1

5

說明

此例最佳是 a 改 b、d 改 e，然後兩個 e 都改 c。共需 $1+4+0+0=5$ 天，最終字串 bbccc。

子任務

• 測試點 2–4 滿足 $N\le 1000, K\le 50.$
• 測試點 5–8 滿足 $N\le 30,000, K\le 50.$

題目作者：Eric Wei