H. Подпоследовательности (усложненная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — ограничения.

Подпоследовательность строки может быть получена из другой строки при помощи удаления некоторого (возможно, нулевого) количества символов без изменения порядка оставшихся символов. Удаляемые символы не обязательно должны идти друг за другом, между ними могут быть любые пропуски. Например, для строки «abaca» следующие строки являются ее подпоследовательностями: «abaca», «aba», «aaa», «a» и «» (пустая строка). А следующие строки не являются подпоследовательностями: «aabaca», «cb» и «bcaa».

Вам задана строка $$$s$$$, состоящая из $$$n$$$ строчных букв латинского алфавита.

За один ход вы можете выбрать любую подпоследовательность $$$t$$$ заданной строки и добавить ее во множество $$$S$$$. Множество $$$S$$$ не может содержать одинаковых элементов. Этот ход стоит $$$n - |t|$$$, где $$$|t|$$$ равно длине добавляемой подпоследовательности (то есть цена равна количеству удаленных символов).

Ваша задача — найти минимальную возможную суммарную стоимость получения множества $$$S$$$ размера $$$k$$$ или сообщить, что это сделать невозможно.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 10^{12}$$$) — длину строки и размер множества соответственно.

Вторая строка входных данных содержит строку $$$s$$$, состоящую из $$$n$$$ строчных букв латинского алфавита.

Выходные данные

Выведите одно целое число — если невозможно составить множество $$$S$$$ размера $$$k$$$, выведите -1. Иначе выведите минимально возможную суммарную стоимость составления такого множества.

Примеры
Входные данные
4 5
asdf
Выходные данные
4
Входные данные
5 6
aaaaa
Выходные данные
15
Входные данные
5 7
aaaaa
Выходные данные
-1
Входные данные
10 100
ajihiushda
Выходные данные
233
Примечание

В первом тестовом примере мы можем составить $$$S$$$ = { «asdf», «asd», «adf», «asf», «sdf» }. Стоимость первого элемента в $$$S$$$ равна $$$0$$$, а стоимости остальных равны $$$1$$$. Таким образом, суммарная стоимость $$$S$$$ равна $$$4$$$.