Моортал Каубат

Бесси уже долгое время играет в популярную игру Moortal Cowmbat. Однако недавно разработчики игры выпустили обновление, которое вынуждает Бесси изменить свой стиль игры.

В игре используются $m$ кнопок, обозначенных первыми $m$ строчными буквами. Любимая комбинация ходов Бесси в игре — это строка $s$ из $n$ нажатий кнопок. Из-за недавнего обновления теперь каждое комбо должно состоять из серии "полос", где полоса определяется как последовательность нажатий одной и той же кнопки не менее $k$ раз подряд. Бесси хочет изменить свою любимую комбинацию так, чтобы создать новую комбинацию такой же длины $n$, но состоящую из серий нажатий кнопок, удовлетворяющих измененным правилам.

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

Помогите Бесси определить наименьшее количество дней, необходимое ей для создания комбинации, отвечающей новым требованиям.

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

Первая строка содержит $n(1\le n\le 10^5)$, $m(1\le m\le 26)$ и $k(1\le k\le n)$. Вторая строка содержит строку $s$, а последние $m$ строк содержат $m\times m$ матрицу значений $a_{ij}$, где $a_{ij}$ — целое число в диапазоне $\mathrm{0...1000}$ и $a_{ii}=0$ для всех $i$.

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

Помогите Бесси определить наименьшее количество дней, которое ей понадобится, чтобы создать комбинацию, удовлетворяющую новым требованиям.

Примеры

Оптимальное решение в этом примере — заменить $a$ на $b$, заменить $d$ на $e$, а затем заменить обе $e$ на $с$. Это займет $1+4+0+0-5$ дней, а последняя строка со списком будет $bbccc$.