Бесси уже давно играет в популярную игру Моортал Каубат. Однако разработчики игры недавно выпустили обновление, которое вынуждает Бесси изменить свой стиль игры.
В игре используются m кнопок, помеченные первыми m строчными буквами. Любимая комбинация ходов Бесси в игре - это строка s из n нажатий кнопок. Однако в связи с последним обновлением каждая комбинация теперь должна состоять из серии "полос", где полоса определяется как последовательность нажатий одной и той же кнопки не менее k раз подряд. Бесси хочет изменить свою любимую комбинацию так, чтобы создать новую комбинацию такой же длины n, но сделанную из серии нажатий кнопок, удовлетворяющих измененным правилам.
Бесси требуется a[ij]
дней, чтобы научиться нажимать кнопку j вместо кнопки i в любом конкретном месте в ее комбинации (то есть стоит a[ij]
изменить одну конкретную букву в s с i на j). Обратите внимание, что переключение с кнопки i на промежуточную кнопку k, а затем с кнопки k на кнопку j может занять меньше времени, чем с i на j напрямую (или например может существовать путь изменений, начинающийся с i и заканчивающийся в j, имеющий меньшую общую стоимость непосредственного переключения с кнопки i на кнопку j).
Помогите Бесси определить наименьшее количество дней, необходимое ей для создания комбинации, отвечающей новым требованиям.
Первая строка содержит n (1 ≤ n ≤ 10^5
), m (1 ≤ m ≤ 26) и k (1 ≤ k ≤ n). Вторая строка содержит строку s, а последние m строк содержат m * m матрицу значений a[ij]
, где a[ij]
- целое число в диапазоне 0 ... 1000 и a[ii]
= 0 для всех i.
Выведите минимальное количество дней, в течение которого Бесси сможет изменить свою комбинацию на такую, которая удовлетворяет новым требованиям.
Оптимальное решение в этом примере - заменить a на b, заменить d на e, а затем заменить оба e на с. Это займет 1 + 4 + 0 + 0 = 5 дней, а последняя строка со списком будет bbccc.