تلعب 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