Вася программирует так интенсивно, что от его ударов по клавиатуре некоторые клавиши с буквами вывалились и не вставляются обратно — такие клавиши он складывал в особый ящик. Клавиатур Вася сломал немало, поэтому некоторые выпавшие клавиши могут встречаться в нескольких экземплярах.
Проводя весеннюю уборку, Вася наткнулся на ящик с клавишами и подсчитал, сколько раз встречается каждая клавиша. Теперь он хочет составить из этих клавиш одну строку и украсить ей интерьер своего кабинета. Вася считает, что чем больше различных подстрок длины k (последовательностей подряд идущих символов длины k) есть в этой строке, тем сильнее эта строка украсит интерьер. Помогите Васе с украшением.
Формат ввода
В первой строке задается количество наборов входных данных T. В этой задаче T всегда равно 1.
В первой строке каждого описания набора дано два целых числа m и k ( 1≤m≤3, 1≤k≤13 ) — число различных типов клавиш и требуемая длина различных подстрок.
В следующих m строках описываются клавиши. Каждое описание состоит из маленькой английской буквы Ci, написанной на клавише, и числа Ti — количества таких клавиш. Гарантируется, что суммарное количество клавиш не превосходит 16.
Формат вывода
Для каждого набора выведите строку, составленную из клавиш. Чем больше в ней различных подстрок длины k — тем выше будет балл.
| № | Входные данные | Выходные данные |
|
1
|
1
2 2
a 2
b 2
|
aabb
|