CF1183H.Subsequences (hard version)

The only difference between the easy and the hard versions is constraints.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols. Characters to be deleted are not required to go successively, there can be any gaps between them. For example, for the string "abaca" the following strings are subsequences: "abaca", "aba", "aaa", "a" and "" (empty string). But the following strings are not subsequences: "aabaca", "cb" and "bcaa".

You are given a string $s$ consisting of $n$ lowercase Latin letters.

In one move you can take any subsequence $t$ of the given string and add it to the set $S$. The set $S$ can't contain duplicates. This move costs $n - |t|$, where $|t|$ is the length of the added subsequence (i.e. the price equals to the number of the deleted characters).

Your task is to find out the minimum possible total cost to obtain a set $S$ of size $k$ or report that it is impossible to do so.

简单版本与困难版本的唯一区别在于约束条件。

子序列是指通过删除原字符串中的一些字符（也可以不删）而得到的字符串，且剩余字符的相对顺序保持不变。被删除的字符不必连续，它们之间可以存在任意间隔。例如，对于字符串 "abaca"，以下字符串均为其子序列："abaca"、"aba"、"aaa"、"a" 和 ""（空字符串）；但以下字符串不是其子序列："aabaca"、"cb" 和 "bcaa"。

你将获得一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

在一次操作中，你可以任取字符串 $s$ 的一个子序列 $t$，并将其加入集合 $S$ 中。集合 $S$ 中不允许出现重复元素。该操作的代价为 $n - |t|$，其中 $|t|$ 表示所添加子序列的长度（即代价等于被删除的字符个数）。

你的任务是：求出获得大小为 $k$ 的集合 $S$ 所需的最小总代价；若无法做到，则报告这是不可能的。

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 100, 1 \le k \le 10^{12}$) — the length of the string and the size of the set, correspondingly.

The second line of the input contains a string $s$ consisting of $n$ lowercase Latin letters.

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100$，$1 \le k \le 10^{12}$），分别表示字符串的长度和集合的大小。

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

Print one integer — if it is impossible to obtain the set $S$ of size $k$, print -1. Otherwise, print the minimum possible total cost to do it.

输出一个整数——如果无法得到大小为 $k$ 的集合 $S$，则输出 $-1$；否则，输出实现该目标的最小总代价。

In the first example we can generate $S$ = { "asdf", "asd", "adf", "asf", "sdf" }. The cost of the first element in $S$ is $0$ and the cost of the others is $1$. So the total cost of $S$ is $4$.

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