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

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

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

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

Формат ввода

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

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

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

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

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

Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Каждый тестовый набор оценивается максимум в 5 баллов. Оценка за набор вычисляется по формуле 5 × ( U s e r A n s B e s t A n s ) 5 5\times (\frac{UserAns}{BestAns})^5 , где B e s t A n s BestAns  — максимальное количество различных подстрок длины k k среди решений всех участников и жюри, а U s e r A n s UserAns  — оличество различных подстрок длины k k в решении участника.