简单版本和困难版本之间的唯一区别是限制。
子序列是可以通过删除一些符号或不删除任何符号而从另一个字符串派生出来的字符串,而不改变剩余符号的顺序。要删除的字符不需要连续,它们之间可以有任何间隙。例如,对于字符串“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$$$。