你是一只压力重重的小老鼠，试图在人工智能初创公司不断加速崛起的浪潮中生存。随着竞争对手四处涌现，获取任何技术优势似乎都变得几乎不可能。在你拼命寻找优势的过程中，你偶然发现了 CheapAI™，这是一家资金极度匮乏的初创公司，甚至连你都雇得起。你的第一个任务是：构建世界上最便宜的分词器（tokenizer）。
你已被 CheapAI™ 聘用，并被分配了构建分词器的任务。不幸的是，预算非常有限，除了 26 个英文小写字母外，你只能再负担一个额外的 token，其长度最多为 $K$。
给你一个由英文小写字母组成的字符串 $S$ 和一个数字 $K$。你的目标是选择一个长度最多为 $K$ 的 token 字符串，使得如果你将该字符串中选择的一些互不重叠的该 token 替换为特殊字符 #，则表示所得字符串所需的总字符数最小。
任务：给定一个数字 $K$ 和一个由英文小写字母组成的字符串 $S$，选择一个非空字符串 $t$，满足 $1 \le |t| \le K$，使得通过将 $S$ 中出现的 $t$（选择若干个，使得任意两个不重叠）替换为特殊字符 #，所得字符串的总长度最小。
确定这个最小长度。
实现细节
你应该实现以下函数：
int solve(int K, std::string S);该函数接收 $K$ 和 $S$ 作为参数，并且必须确定在将所选 token（长度最多为 $K$）的一些（互不重叠的）出现替换为字符 # 后得到的字符串的最小长度。
数据范围
- $1 \le K \le |S| \le 200\,000$
- $S$ 仅包含英文小写字母。
| 子任务 | 分数 | 限制条件 | ||
|---|---|---|---|---|
| 1 | 5 | $S_i = \text{a}$，$1 \le i \le | S | $ |
| 2 | 7 | $ | S | \le 100$ |
| 3 | 12 | $ | S | \le 5000$ |
| 4 | 40 | $ | S | \le 75\,000$ |
| 5 | 36 | 无附加限制 |
样例
输入样例 1
5 aabaabacbbaabaa
输出样例 1
7
说明 1
我们选择 $t = \text{aabaa}$，字符串 $S$ 变为 #bacbb#，长度为 7。
输入样例 2
8 aaaaaaaaaaaaaaaaaaa
输出样例 2
4
说明 2
我们选择 $t = \text{aaaaaa}$，字符串 $S$ 变为 ###a，长度为 4。