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

Бессі вже тривалий час грає в популярну гру 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$.