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

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

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

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

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

Первая строка содержит n (1 ≤ n ≤ 105), m (1 ≤ m ≤ 26) и k (1 ≤ k ≤ n). Вторая строка содержит строку s, а последние m строк содержат m * m матрицу значений aij, где aij - целое число в диапазоне 0 ... 1000 и aii = 0 для всех i.

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

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

Пример

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