Бесі вже довго грає у популярну гру 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\).

Формат вхідних даних

Перший рядок введення містить \(N\), \(M\) та \(K\).

Другий рядок містить \(S\), а останні \(M\) рядків містять матрицю \(M\times M\) значень \(a_{ij}\), де \(a_{ij}\) - ціле число в інтервалі \(0 \ldots 1000\) і \(a_{ii} = 0\) для всіх \(i\).

Формат вихідних даних

Виведіть одне ціле число, що становить мінімальну кількість днів, яке потрібно Бесі для зміни її комбінації так, щоб вона стала задовольняти нові обмеження.

Приклад вхідних даних

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

Оптимальне рішення у цьому прикладі

• змінити a на b, змінити d на e, потім змінити обидва e’s into c’s. Це займе \(1+4+0+0=5\) днів, і фінальний рядок стане be bbccc.