Задача: C2 Уникальные подстроки - 2

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на файл "input.txt".

Вася программирует так интенсивно, что от его ударов по клавиатуре некоторые клавиши с буквами вывалились и не вставляются обратно — такие клавиши он складывал в особый ящик. Клавиатур Вася сломал немало, поэтому некоторые выпавшие клавиши могут встречаться в нескольких экземплярах.

Проводя весеннюю уборку, Вася наткнулся на ящик с клавишами и подсчитал, сколько раз встречается каждая клавиша. Теперь он хочет составить из этих клавиш одну строку и украсить ей интерьер своего кабинета. Вася считает, что чем больше различных подстрок длины k (последовательностей подряд идущих символов длины k) есть в этой строке, тем сильнее эта строка украсит интерьер. Помогите Васе с украшением.

Формат ввода

В первой строке задается количество наборов входных данных T. В этой задаче T равно 10.

В первой строке каждого описания набора дано два целых числа m и k ( 1≤m≤10, 1≤k≤13) — число различных типов клавиш и требуемая длина различных подстрок.

В следующих mm строках описываются клавиши. Каждое описание состоит из маленькой английской буквы C_i​, написанной на клавише, и числа T_i — количества таких клавиш. Гарантируется, что суммарное количество клавиш не превосходит 10 00010000.

Формат вывода

Для каждого набора выведите строку, составленную из клавиш. Чем больше в ней различных подстрок длины k — тем выше будет балл.

Ваш ответ: