← 返回题目列表

Codeforces · 1183/H

H. 子序列(硬版本)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

子序列是可以通过删除一些符号或不删除任何符号而从另一个字符串派生出来的字符串,而不改变剩余符号的顺序。要删除的字符不需要连续,它们之间可以有任何间隙。例如,对于字符串“abaca”,以下字符串是子序列:“abaca”、“aba”、“aaa”、“a”和“”(空字符串)。但以下字符串不是子序列:“aabaca”、“cb”和“bcaa”。

给你一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

只需一步,您就可以获取给定字符串的任何子序列 $$$t$$$ 并将其添加到集合 $$$S$$$ 中。集合 $$$S$$$ 不能包含重复项。此移动成本 $$$n - |t|$$$,其中 $$$|t|$$$ 是添加的子序列的长度(即价格等于删除的字符数)。

你的任务是找出获得一组大小为 $$$k$$$ 的 $$$S$$$ 的最低可能总成本,或者报告不可能这样做。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 10^{12}$$$) — 相应地,字符串的长度和集合的大小。

输入的第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

输出

打印一个整数 — 如果无法获得大小为 $$$k$$$ 的集合 $$$S$$$,则打印 -1。否则,打印完成该任务的最小可能总成本。

示例

输入 #1

4 5
asdf

输出 #1

4

输入 #2

5 6
aaaaa

输出 #2

15

输入 #3

5 7
aaaaa

输出 #3

-1

输入#4

10 100
ajihiushda

输出#4

233

注意

在第一个示例中,我们可以生成 $$$S$$$ = { "asdf", "asd", "adf", "asf", "sdf" }。 $$$S$$$ 中第一个元素的成本为 $$$0$$$,其他元素的成本为 $$$1$$$。因此 $$$S$$$ 的总成本为 $$$4$$$。