Беси уже долго играет в популярную игру Moortal Cowmbat.
Однако недавно разработчики выпустили обновление игры, которое заставило
Беси изменить свой стиль игры.
Игра использует \(M\) клавиш, помеченных первыми \(M\) маленькими латинскими
буквами (\(1 \leq M \leq 26\)). Любимая комбинация ходов Беси в этой игре
это строка \(S\) длиной \(N\) (\(1 \leq N \leq 10^5\)), описывающая нажатые клавиши.
Однако в связи с обновлением игры каждая комбинация теперь должна состоять
из серий "полос", где "полоса" определяется как серия нажатий одной и той же клавиши
не менее \(K\) раз подряд (\(1 \leq K \leq N\)). Беси хочет модифицировать её любимую
комбинацию такой же длины \(N\), на сделанную из полос клавиш, удовлетворяющих
введённым правилам.
\(a_{ij}\) дней требуется Беси, чтобы научиться нажимать клавишу \(j\) вместо
клавиши \(i\) в любом месте её комбинации (то есть это стоит \(a_{ij}\) -
изменить один символ в строке \(S\) c \(i\) на \(j\)). Заметим, что может так оказаться,
что выгоднее (меньше дней) переключиться на использование с \(i\) на промежуточную
клавишу \(k\) и затем с \(k\) на \(j\), чем непосредственно переключаться с \(i\) на \(j\)
(или, обобщая, может быть путь изменений, начинающийся с \(i\) и заканчивающийся в \(j\), который обеспечивает более выгодную стоимость (меньшее количество дней), чем непосредственное переключение с клавиши \(i\) на клавишу \(j\)).
Помогите Беси определить минимально возможное количество дней, которое требуется ей, чтобы создать комбинацию, удовлетворяющую новым ограничениям.
ОЦЕНИВАНИЕ:
- Тесты 2-4 удовлетворяют \(N\le 1000, K\le 50\).
- тесты 5-8 удовлетворяют \(N\le 30,000, K\le 50\).
ФОРМАТ ВВОДА (файл cowmbat.in):
Первая строка ввода содержит \(N\), \(M\) и \(K\). Вторая строка содержит
\(S\), а последние \(M\) строк содержат матрицу \(M\times M\) значений \(a_{ij}\),
где \(a_{ij}\) - целое число в интервале \(0 \ldots 1000\) и \(a_{ii} = 0\)
для всех \(i\).
ФОРМАТ ВЫВОДА (файл cowmbat.out):
Выведите одно целое число, представляющее минимальное количество дней,
которое требуется Беси для изменения её комбинации так, чтобы она стала
удовлетворять новым ограничениям.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
5
|