题目描述

这是该问题的简单版本。唯一的区别在于 $n$ 和 $k$ 的约束条件。只有在所有版本的问题都被解决后，你才能进行 hack。

你有一个字符串 $s$，你可以对它进行两种操作：

• 删除字符串的最后一个字符。
• 复制字符串：$s := s + s$，其中 $+$ 表示连接操作。

每种操作你都可以执行任意次（也可以不执行）。

你的任务是通过对字符串 $s$ 进行这些操作，得到长度恰好为 $k$ 的字典序最小的字符串。

如果满足以下任一条件，则字符串 $a$ 的字典序小于字符串 $b$：

• $a$ 是 $b$ 的前缀，且 $a \ne b$；
• 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 5000$）——原始字符串 $s$ 的长度和所需字符串的长度。

第二行包含字符串 $s$，由 $n$ 个小写英文字母组成。

输出格式

输出通过对字符串 $s$ 进行操作后得到的长度恰好为 $k$ 的字典序最小的字符串。

说明/提示

在第一个测试中，最优方案是进行一次复制操作："dbcadabc" $\to$ "dbcadabcdbcadabc"。

在第二个测试中，最优方案是先删除最后 $3$ 个字符，然后将字符串复制 $3$ 次，再删除最后 $3$ 个字符，使字符串长度为 $k$。

"abcd" $\to$ "abc" $\to$ "ab" $\to$ "a" $\to$ "aa" $\to$ "aaaa" $\to$ "aaaaaaaa" $\to$ "aaaaaaa" $\to$ "aaaaaa" $\to$ "aaaaa"。

由 ChatGPT 4.1 翻译

样例

8 16
dbcadabc

dbcadabcdbcadabc

4 5
abcd

aaaaa