ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2024. Время приключений

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
«Получай!» — крикнул Финн, сражаясь с Теневыми Стражами, — «Джейк! Быстрее собирай Камни Тьмы и бежим отсюда!»
Джейк был бы рад закончить побыстрее, ведь в Опасной Пещере было сыро и грустно, но сбор Камней оказался не такой уж простой задачей. Поэтому он позвонил БиМо и попросил его помочь выбрать оптимальный набор Камней. Джейк рассказал БиМо о том, что всего в пещере лежат n камней, пронумерованных различными целыми числами от 1 до n, каждый из которых покрашен в один из 26 цветов. Также Джейк напомнил БиМо о предупреждении принцессы Бубльгум: среди вынесенных из пещеры Камней должно быть не более k штук, имеющих попарно различные цвета. Только множество Камней, обладающее этим свойством, является безопасным. Если же вынести из пещеры небезопасное множество Камней, будет разбужено Вселенское Зло! Разумеется, Джейк не хочет будить Зло, но хочет вынести как можно больше Камней Тьмы из Пещеры. Попробуйте поставить себя на место БиМо и найдите размер наибольшего безопасного множества Камней и количество различных безопасных множеств такого размера. Два множества Камней следует считать различными, если в одном из них есть Камень с номером, которого нет в другом множестве.

Исходные данные

В первой строке записано n строчных латинских букв (1 ≤ n ≤ 105), каждая буква обозначает цвет Камня. Во второй строке дано целое число k (1 ≤ k ≤ 26).

Результат

Выведите два целых числа, разделённых пробелом: размер наибольшего безопасного множества Камней Тьмы и количество различных безопасных множеств такого размера.

Примеры

исходные данныерезультат
abcde
1
1 5
ababac
2
5 1
Автор задачи: Никита Сивухин
Источник задачи: Уральская региональная командная олимпиада по программированию 2014