Erase and Extend (Easy Version)
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 1600
Tags: binary search, brute force, dp, greedy, hashing, implementation, string suffix structures, strings, two pointers

This is the easy version of the problem. The only difference is the constraints on $$$n$$$ and $$$k$$$. You can make hacks only if all versions of the problem are solved.

You have a string $$$s$$$, and you can do two types of operations on it:

- Delete the last character of the string.
- Duplicate the string: $$$s:=s+s$$$, where $$$+$$$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $$$k$$$ that can be obtained by doing these operations on string $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a\ne b$$$;
- In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input format:
The first line contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5000$$$) — the length of the original string $$$s$$$ and the length of the desired string.

The second line contains the string $$$s$$$, consisting of $$$n$$$ lowercase English letters.

Output format:
Print the lexicographically smallest string of length $$$k$$$ that can be obtained by doing the operations on string $$$s$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, it is optimal to make one duplication: "dbcadabc" $$$\to$$$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $$$3$$$ characters, then duplicate the string $$$3$$$ times, then delete the last $$$3$$$ characters to make the string have length $$$k$$$.

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

Example input:
8 16
dbcadabc

Example output:
dbcadabcdbcadabc

Example input:
4 5
abcd

Example output:
aaaaa

Editorial:
We claim that it is optimal to choose a prefix of the string, then duplicate it until we have a length bigger than $$$k$$$, then delete the excess elements.
Let's relax the requirement so you have a position in the string and each time you either return to the beginning or advance to the next character. The answer will be the first k characters of the lexicographically smallest infinite string. From a given position, the optimal infinite string from it is unique, so you can pick exactly one optimal decision. Now the optimal string is going around some cycle from the start, and we see it also satisfies the original requirement, not just our relaxation
We proved that it is optimal to choose a prefix, duplicate it until the length is bigger than k then delete the excess. As the constraints are low, we can iterate through every prefix on the original string and make a string of length $$$k$$$ with it. Then we take the minimum of all these strings as the answer. Solution complexity $$$O(n\cdot k)$$$.