Bessie משחקת כבר זמן רב במשחק הקרבות הפופולרי Moortal Cowmbat. אך עדכון אחרון מאלץ אותה לשנות את סגנון המשחק.

יש $M$ כפתורים, $M$ האותיות הקטנות הראשונות ($1 \leq M \leq 26$). רצף המהלכים האהוב הוא מחרוזת $S$ באורך $N$ ($1 \leq N \leq 10^5$). כעת כל רצף חייב להיות מורכב מ״סדרות״: לחיצה על אותו כפתור לפחות $K$ פעמים רצופות ($1 \leq K \leq N$). היא רוצה לשנותו תוך שמירת האורך $N$ וליצור סדרות תקינות.

אימון ללחוץ $j$ במקום $i$ במיקום מסוים לוקח $a_{ij}$ ימים, עלות שינוי אות מסוימת אחת ב־$S$ מ־$i$ ל־$j$. מעבר מ־$i$ דרך כפתור ביניים $k$ ואז ל־$j$ עשוי להיות מהיר יותר מישיר. בכלל, שרשרת שינויים מ־$i$ ל־$j$ עשויה לתת עלות כוללת מיטבית.

מצאו את מספר הימים המזערי ליצירת רצף תקין.

קלט

השורה הראשונה מכילה $N$, $M$, $K$, השנייה $S$, והאחרונות $M$ מטריצת $M\times M$ של שלמים $a_{ij}$ בתחום $0 \ldots 1000$, עם $a_{ii} = 0$ לכל $i$.

פלט

הדפיסו מספר אחד, הימים המזעריים לשינוי הרצף כך שיקיים את הדרישות.

דוגמאות

קלט 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

פלט 1

5

הסבר

המיטבי משנה a ל־b, d ל־e, ואז את שתי e ל־c. זה לוקח $1+4+0+0=5$ ימים ונותן bbccc.

ניקוד

• מקרים 2–4: $N\le 1000, K\le 50.$
• מקרים 5–8: $N\le 30,000, K\le 50.$

מחבר הבעיה: Eric Wei