Bessie давно играет в популярный файтинг Moortal Cowmbat. Но недавнее обновление заставляет её изменить стиль игры.

В игре $M$ кнопок, первых $M$ строчных букв ($1 \leq M \leq 26$). Любимое комбо — строка $S$ длины $N$ ($1 \leq N \leq 10^5$). Теперь комбо должно состоять из «серий»: одна кнопка нажата подряд хотя бы $K$ раз ($1 \leq K \leq N$). Она хочет изменить любимое комбо, сохранив длину $N$, чтобы оно состояло из таких серий.

Обучение нажимать $j$ вместо $i$ в конкретной позиции занимает $a_{ij}$ дней: столько стоит изменить одну букву $S$ с $i$ на $j$. Переход через промежуточную кнопку $k$, сначала $i$ в $k$, затем $k$ в $j$, может быть быстрее прямого. Вообще цепочка переходов от $i$ до $j$ может давать лучшую общую стоимость.

Найдите минимальное число дней для создания допустимого комбо.

Входные данные

Первая строка — $N$, $M$, $K$, вторая — $S$, последние $M$ — матрица $M\times M$ значений $a_{ij}$, целых в $0 \ldots 1000$, с $a_{ii} = 0$ для всех $i$.

Выходные данные

Выведите одно число — минимальное число дней изменения комбо для новых требований.

Примеры

Входные данные 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