Единственное отличие между легкой и сложной версиями — ограничения.
Подпоследовательность строки может быть получена из другой строки при помощи удаления некоторого (возможно, нулевого) количества символов без изменения порядка оставшихся символов. Удаляемые символы не обязательно должны идти друг за другом, между ними могут быть любые пропуски. Например, для строки «abaca» следующие строки являются ее подпоследовательностями: «abaca», «aba», «aaa», «a» и «» (пустая строка). А следующие строки не являются подпоследовательностями: «aabaca», «cb» и «bcaa».
Вам задана строка \(s\), состоящая из \(n\) строчных букв латинского алфавита.
За один ход вы можете выбрать любую подпоследовательность \(t\) заданной строки и добавить ее во множество \(S\). Множество \(S\) не может содержать одинаковых элементов. Этот ход стоит \(n - |t|\), где \(|t|\) равно длине добавляемой подпоследовательности (то есть цена равна количеству удаленных символов).
Ваша задача — найти минимальную возможную суммарную стоимость получения множества \(S\) размера \(k\) или сообщить, что это сделать невозможно.
Примечание
В первом тестовом примере мы можем составить \(S\) = { «asdf», «asd», «adf», «asf», «sdf» }. Стоимость первого элемента в \(S\) равна \(0\), а стоимости остальных равны \(1\). Таким образом, суммарная стоимость \(S\) равна \(4\).