After freeing himself from the clutches of HYDRA, Bucky is now finally a free man. And now he decided that he must destroy HYDRA so that no one else has to suffer. To destroy HYDRA, he must first find the secret passcode to enter their safehouse.
Bucky has already managed to get hold of a secret list of patterns, and the threshold N, a positive integer. The passcode is a string for which the summation of the number of occurrences of all the patterns in the string is greater than the threshold N. If there are multiple such strings, the answer is the lexicographically smallest string.
Formally, you are given an integer N and a list of patterns of size K, where each pattern is a string consisting of lowercase English alphabets. Let’s call these strings P1, P2, P3 … PK. Also, define Occurrence(S, P) where S and P are two strings, as the number of substrings of S equal to P.
You need to find the smallest string S, such that N ≤ ∑ Occurrence(S, Pi). If there are multiple such strings, output the lexicographically smallest string S.
Here the patterns need not be unique so that a pattern might appear multiple times, and the summation would count separately for each pattern.
Input
The first line contains two integers N and K.
Then K lines follow, where the ith line contains the ith pattern, Pi.
Constraints:
1 ≤ N ≤ 100
1 ≤ ∑|Pi| ≤ 1000
Output
Output the string of the smallest length, satisfying the constraints as mentioned above.
If there are multiple such strings, output the lexicographically smallest one.