嘤嘤的棒子

题号：NC250232
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

嘤嘤在某知名 ~~同性交友~~ 网站上做了一道某知名出题人的题，做完大呼好题，当即决定把这题韩国了！（Ctrl+H，小红 $\rightarrow$ 嘤嘤，Enter！所以，这是不是也叫韩红题？所以原题的出题人是谁呢？）

世界名画——《亿点点》（熊猫头）（图片加载失败）

嘤嘤定义一个字符串的回文值是：每次修改一个字符，将该字符串变成回文串的最少操作次数。例如"abcb"的“回文值”是2（将其修改为acca即可，需要修改2次），而"baecb"的回文值是1（修改为baeab即可，只需要修改1次）。

嘤嘤拿到了一个由小写字母和 ',' 、 '.' 、 '!' 、 '?' 四种标点符号组成的字符串 $str$ 。她想先定义最多 $k$ 种命运字符（命运字符不一定要在字符串出现过），对于该字符串出现的所有命运字符，嘤嘤可以随意将其修改为任意字符。在修改完之后，嘤嘤希望该字符串的回文值尽可能小。

嘤嘤想知道，最终回文值最小值是多少？

PS：本题原本是一个签到题，但是某不愿透露姓名的沙姓毒瘤觉得这场比赛过于简单，于是决定增加难度，因此修改了此题（冤有头，债有主！），并希望缩减本题的时间限制，但善良的嘤嘤决定多给你一些时间，还不快说——谢谢超级无敌世界第一巨TM可爱的嘤嘤♪。

第一行输入两个正整数  ，分别代表字符串长度，以及嘤嘤可以选择的命运字符数量。

第二行输入一个长度为  的、仅由小写字母和 ',' 、 '.' 、 '!' 、 '?' 四种标点符号组成的字符串。

嘤嘤选择了命运字符并进行修改后，字符串回文值的最小值。

示例1

复制

5 1
djwcb

复制

选择b作为命运字符即可，此时嘤嘤可以修改第五个字符。若将字符串修改为"djwcd"，则回文值是1。

示例2

复制

8 5
yykawaii

复制

选择y、k、a、w、i作为命运字符，此时由于所有字符都是命运字符，所以嘤嘤可以将该字符串修改为任意字符串。嘤嘤将其修改为"yyyyyyyy"，此时回文值是0。

示例3

复制

8 2
yykawaii

复制

选择 y , a 作为命运字符，将两个 y 都改成 i ，第一个 a 改成 w ，第二个 a 改成 k ，即可将原字符串修改为 "iikwwkii" ，此时回文值是 0 。

示例4

复制

26 26
i,am,kamisato,ayaka,s,dog!

复制