Ограничение времени | 5 секунд |
Ограничение памяти | 64 Мб |
Ввод | стандартный ввод или input.txt |
Вывод | стандартный вывод или output.txt |
В этой задаче на проверку необходимо сдать исходный код программы.
Вася программирует так интенсивно, что от его ударов по клавиатуре некоторые клавиши с буквами вывалились и не вставляются обратно — такие клавиши он складывал в особый ящик. Клавиатур Вася сломал немало, поэтому некоторые выпавшие клавиши могут встречаться в нескольких экземплярах.
Проводя весеннюю уборку, Вася наткнулся на ящик с клавишами и подсчитал, сколько раз встречается каждая клавиша. Теперь он хочет составить из этих клавиш одну строку и украсить ей интерьер своего кабинета. Вася считает, что чем больше различных подстрок длины (последовательностей подряд идущих символов длины ) есть в этой строке, тем сильнее эта строка украсит интерьер. Помогите Васе с украшением.
В первой строке задается количество наборов входных данных . В этой задаче всегда равно 1.
В первой строке каждого описания набора дано два целых числа и ( , ) — число различных типов клавиш и требуемая длина различных подстрок.
В следующих строках описываются клавиши. Каждое описание состоит из маленькой английской буквы , написанной на клавише, и числа — количества таких клавиш. Гарантируется, что суммарное количество клавиш не превосходит .
Для каждого набора выведите строку, составленную из клавиш. Чем больше в ней различных подстрок длины — тем выше будет балл.
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждый тестовый набор оценивается максимум в 5 баллов. Оценка за набор вычисляется по формуле , где — максимальное количество различных подстрок длины среди решений всех участников и жюри, а — оличество различных подстрок длины в решении участника.
Ввод | Вывод |
---|---|
1 2 2 a 2 b 2 | aabb |