Смешной язык
Известна популярная игра со словами. Вам даётся слово, и ваша задача — составить как можно больше других слов, используя буквы из данного слова. Если в оригинальном слове буква встречается несколько раз, вы можете использовать её столько же раз в новых словах. Порядок букв в оригинальном слове не имеет значения. Например, если дано слово CONTEST, вы можете составить слова NOTE, NET, ON, TEST, SET и так далее.
Теперь вы должны создать новый словарь. Ваша задача — добавить в него n новых слов. У вас уже есть m слов Wi (1 <=i<=m), с которыми вы будете работать, и вам нужно определить, какие n новых слов добавить в словарь, чтобы максимизировать общее количество слов, которые можно составить из этих m слов.
Более формально, найдите такой набор непустых слов S, где |S| = n, W_i S для любого i, и ∑_1_{≤}_i_{≤}_m |S_i| максимальна, где Si S — это набор слов, которые можно составить, используя буквы из Wi.
Входные данные
Первая строка входного файла содержит два целых числа n (1 <=n<= 100) — количество новых слов, которые вы можете добавить в словарь, и m (1 <=m<= 1 000) — количество слов, с которыми вы будете работать. Следующие m строк содержат оригинальные слова. Каждое слово состоит из не более чем 100 заглавных букв от A до Z.
Выходные данные
Выведите в выходной файл n строк, в каждой из которых будет новое слово.