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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
4 5
asdf

Output
4

Input
5 6
aaaaa

Output
15

Input
5 7
aaaaa

Output
-1

Input
10 100
ajihiushda

Output
233



-----Note-----

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$.

Difficulty: introductory

Starter code:

Solutions:
def sol(a,k):
    n=len(a)
    if(k==0):return 1
    if(k==1):
        v=set()
        for x in a:
            v.add(x)
        return len(v)
    if(n<k or n<1 or k<1):
        return 0
    if(n==k):
        return 1
    sz=max(3000,n)
    v1=[0]*sz
    v2=[0]*sz
    v3=[0]*sz
    v2[n-1]=1
    v3[a[n-1]-1]=1
    for i in range(n-2,-1,-1):
        if(i<0):break
        v2[i]=v2[i+1]
        if(v3[a[i]-1]==0):
            v2[i]+=1
            v3[a[i]-1]=1
    for j in range(1,k):
        v3=[0]*sz
        v1[n-1]=0
        for i in range(n-2,-1,-1):
            v1[i]=v1[i+1]
            v1[i]=v1[i]+v2[i+1]
            v1[i] = v1[i] - v3[a[i] - 1]
            v3[a[i] - 1] = v2[i + 1]
        v2=v1.copy()
    return v1[0]
n,k=list(map(int,input().split()))
s=input()
ar=[]
for x in s:
    ar.append(ord(x))
ans=0
cur=n
while cur>=0:
    mx=min(k,sol(ar,cur))
    k-=mx
    ans+=(n-cur)*mx
    cur-=1
if(k!=0):
    print(-1)
else:
    print(ans)


import sys
input = sys.stdin.readline

n,W=list(map(int,input().split()))
s=input().strip()

NEXTLIST=[[n]*26 for i in range(n+1)]

for i in range(n-1,-1,-1):
    for j in range(26):
        NEXTLIST[i][j]=NEXTLIST[i+1][j]
    NEXTLIST[i][ord(s[i])-97]=i

DP=[[0]*(n+1) for i in range(n+1)]

DP[0][0]=1

for i in range(n):
    for j in range(26):
        if NEXTLIST[i][j]!=n:
            for k in range(n):
                DP[NEXTLIST[i][j]+1][k+1]+=DP[i][k]

#print(DP)

HLIST=[0]*(n+1)

for i in range(n+1):
    for j in range(n+1):
        HLIST[j]+=DP[i][j]

#print(HLIST)

ANS=0
for i in range(n,-1,-1):
    #print(i,W)
    if W>HLIST[i]:
        ANS+=(n-i)*HLIST[i]
        W-=HLIST[i]
    else:
        ANS+=W*(n-i)
        print(ANS)
        return

else:
    print(-1)


# @author 

import sys

class HSubsequencesHardVersion:
    def solve(self):
        n, k = [int(_) for _ in input().split()]
        s = input()
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        last = {key: -1 for key in (chr(x) for x in range(ord('a'), ord('z') + 1))}
        for i in range(1, n + 1):
            dp[i][0] = 1
            for j in range(1, i + 1):
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - (dp[last[s[i - 1]]][j - 1] if last[s[i - 1]] != -1 else 0)
            last[s[i - 1]] = i - 1

        ans = 0
        tot = 0
        for sz in range(n, -1, -1):
            ans += min(k - tot, dp[n][sz]) * (n - sz)
            tot = min(k, tot + dp[n][sz])
            if tot == k:
                break

        if tot >= k:
            print(ans)
        else:
            print(-1)

solver = HSubsequencesHardVersion()
input = sys.stdin.readline

solver.solve()


import sys
import itertools

inputs = sys.stdin.read().split()
len_string = int(inputs[0])
desired_size = int(inputs[1])
string = inputs[2]

def val_of_letter(char): return ord(char)-ord("a")

num_subsequences = [1]
num_subsequences_so_far = [0]*len_string
last_num_subsequences_so_far = [0]*len_string
num_subsequences_for_this_letter_so_far = [0]*26

last_num_subsequences_so_far[len_string-1] = 1;
num_subsequences_for_this_letter_so_far[val_of_letter(string[-1])] = 1;

for i in range(len_string-2, -1, -1):
    last_num_subsequences_so_far[i] = \
        last_num_subsequences_so_far[i+1]
    if num_subsequences_for_this_letter_so_far[val_of_letter(string[i])] == 0:
         last_num_subsequences_so_far[i] += 1
         num_subsequences_for_this_letter_so_far[val_of_letter(string[i])] = 1
num_subsequences.append(last_num_subsequences_so_far[0])

for length in range(2, len_string+1):
    for i in range(26): num_subsequences_for_this_letter_so_far[i] = 0
    
    num_subsequences_so_far[len_string-1] = 0
    for i in range(len_string-2, -1, -1):
        num_subsequences_so_far[i] = \
            num_subsequences_so_far[i+1] + \
            last_num_subsequences_so_far[i+1] - \
            num_subsequences_for_this_letter_so_far[val_of_letter(string[i])]
        # print(length, i, num_subsequences_so_far[i], num_subsequences_so_far[i+1], last_num_subsequences_so_far[i+1], num_subsequences_for_this_letter_so_far[val_of_letter(string[i])])
        num_subsequences_for_this_letter_so_far[val_of_letter(string[i])] = \
            last_num_subsequences_so_far[i+1]
    # print()
    
    num_subsequences.append(num_subsequences_so_far[0])
    for i in range(len_string):
         last_num_subsequences_so_far[i] = num_subsequences_so_far[i]

# print(num_subsequences)
size = 0
cost = 0
for i in range(len_string, -1, -1):
    cur_size = num_subsequences[i]
    if size+cur_size >= desired_size:
        cost += (desired_size-size)*(len_string-i)
        size = desired_size
        break
    cost += cur_size*(len_string-i)
    size += cur_size

if size >= desired_size: sys.stdout.write(str(cost)+"\n")
else: sys.stdout.write("-1\n")


line1 = input().split(' ')
n = int(line1[0])
k = int(line1[1])
s = list(input())

dp = [101*[0] for i in range(101)]
last = 26*[-1]

for i in range(n+1):
    dp[0][i] = 1

for l in range(1, n+1):
    dp[l][0] = 0
    for c in range(26):
        last[c] = -1
    for i in range(1, n+1):
        dp[l][i] = dp[l-1][i-1] + dp[l][i-1]
        if last[ord(s[i-1])-ord('a')] != -1:
            dp[l][i] -= dp[l-1][last[ord(s[i-1])-ord('a')]-1]
        last[ord(s[i-1])-ord('a')] = i

i = 0
res = 0
while i <= n and k >= 0:
    c = min(k, dp[n-i][n])
    k -= c
    res += c * i
    i += 1
if k > 0:
    print(-1)
else:
    print(res)


n, tt = list(map(int, input().split()))
s = input()

dp = [[0]*(n + 1) for i in range(n+1)]

for c in range(n+1):
	dp[0][c] = 1

last = [-1]*26

for c in range(1, n + 1):
	k = ord(s[c-1]) - ord('a')
	for r in range(1, n+1):
		dp[r][c] = dp[r][c-1] + dp[r-1][c-1]
	if last[k] == -1:
		last[k] = c - 1
		continue
	else:
		p = last[k]
		for r in range(1, n+1):
			dp[r][c] = dp[r][c] - dp[r-1][p]
		last[k] = c-1

su, ans, t = 0, 0, 0
for r in range(n+1):
	su = su + dp[r][n]
if su < tt:
	ans = -1
else:
	for i in range(n, -1, -1):
		r = min(tt, dp[i][n])
		ans += t*r
		tt -= r
		t += 1

print(ans) 


[n, k] = [int(i) for i in input().split()]
s = input()
cntsz = [0 for i in range(105)]
dp = [[0 for i in range(105)] for j in range(105)]
lst = [0 for i in range(105)]
prv = [0 for i in range(26)]
n = len(s)
s = '%' + s
for i in range(n + 1):
  dp[i][0]=1
for i in range(1, n + 1):
	lst[i] = prv[ord(s[i])-ord('a')]
	prv[ord(s[i]) - ord('a')] = i
for sz in range(1, n + 1):
	for i in range(1, n + 1):
		dp[i][sz] += dp[i - 1][sz]
		dp[i][sz] += dp[i - 1][sz - 1]
		if lst[i] != 0:
			 dp[i][sz] -= dp[lst[i]-1][sz-1]
for sz in range(1, n + 1):
	for i in range(1, n + 1):
		cntsz[sz] += dp[i][sz]
		cntsz[sz] -= dp[i - 1][sz]
cntsz[0] += 1
done = 0
ans = 0
for i in range(n, -1, -1):
    if done + cntsz[i] >= k:
       ans += (n - i) * (k - done)
       done = k
       break
    done += cntsz[i]
    ans += cntsz[i] * (n - i)
if done < k:
    print(-1)
else:
    print(ans)

n, k = list(map(int, input().split()))
s = "$" + input()

cnt = [[0]*(n+1) for i in range(n+1)]

cnt[0][0] = 1

for l in range(1, n+1):
	for i in range(l, n+1):
		used = [False] * 26
		for j in range(i, n+1):
			x = ord(s[j]) - ord('a')
			if not used[x]:
				cnt[l][j] += cnt[l-1][i-1]
				used[x] = True

ans = 0
for l in range(n, -1, -1):
	s = sum(cnt[l])
	if s < k:
		ans += (n-l) * s
		k -= s
	else:
		ans += (n-l) * k
		k = 0
		break

if k > 0: ans = -1

print(ans)


n, k = map(int, input().split())
s = "$" + input()

cnt = [[0]*(n+1) for i in range(n+1)]

cnt[0][0] = 1

for l in range(1, n+1):
	for i in range(l, n+1):
		used = [False] * 26
		for j in range(i, n+1):
			x = ord(s[j]) - ord('a')
			if not used[x]:
				cnt[l][j] += cnt[l-1][i-1]
				used[x] = True

ans = 0
for l in range(n, -1, -1):
	s = sum(cnt[l])
	if s < k:
		ans += (n-l) * s
		k -= s
	else:
		ans += (n-l) * k
		k = 0
		break

if k > 0: ans = -1

print(ans)

n, k = list(map(int, input().split(' ')))
s = input()
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for l in range(0, n):
    for i in range(l, n + 1):
        used = [False] * 26
        for j in range(i + 1, n + 1):
            ch = ord(s[j - 1]) - ord('a')
            if not used[ch]:
                dp[l + 1][j] += dp[l][i]
                used[ch] = True
total = 0
for l in range(n, -1, -1):
    sums = sum(dp[l])
    if sums >= k:
        total += (n - l) * k
        k = 0
        break
    total += (n - l) * sums
    k -= sums
if k > 0:
    total = -1
print(total)


n,k=map(int,input().split())
s=input()
s=[ord(c)-ord('a') for c in s]
dp=[[[0]*26 for i in range(n+1)]for i in range(n)]
dp[0][1][s[0]]=1
sm=None

for i in range(1,n):
    c=s[i]
    for cc in range(26):
        dp[i][1][cc]=dp[i-1][1][cc]
    dp[i][1][c]=1
    for j in reversed(range(2,n+1)):
        for cc in range(26):
            if cc!=c:
                dp[i][j][cc]=dp[i-1][j][cc]
            else:
                tm=0
                for t in range(26):
                    tm+=dp[i-1][j-1][t]
                dp[i][j][cc]=tm
# print(dp[-1][-1])
def get(x):
    if x==0:
        return 1
    ans=0
    for i in range(26):
        ans+=dp[-1][x][i]
    return ans
cnt=0
cost=0
for re in reversed(range(n+1)):
    x=get(re)
    if x+cnt>=k:
        cost+=(n-re)*(k-cnt)
        cnt=k
        break
    else:
        cost+=(n-re)*x
        cnt+=x
if cnt<k:
    print(-1)
else:
    print(cost)

n,k=map(int,input().split())
s=input()
s=[ord(c)-ord('a') for c in s]
dp=[[[0]*26 for i in range(n+1)]for i in range(n)]
dp[0][1][s[0]]=1
sm=None

for i in range(1,n):
    c=s[i]
    for cc in range(26):
        dp[i][1][cc]=dp[i-1][1][cc]
    dp[i][1][c]=1
    for j in reversed(range(2,n+1)):
        for cc in range(26):
            if cc!=c:
                dp[i][j][cc]=dp[i-1][j][cc]
            else:
                tm=0
                for t in range(26):
                    tm+=dp[i-1][j-1][t]
                dp[i][j][cc]=tm
# print(dp[-1][-1])
def get(x):
    if x==0:
        return 1
    ans=0
    for i in range(26):
        ans+=dp[-1][x][i]
    return ans
cnt=0
cost=0
for re in reversed(range(n+1)):
    x=get(re)
    if x+cnt>=k:
        cost+=(n-re)*(k-cnt)
        cnt=k
        break
    else:
        cost+=(n-re)*x
        cnt+=x
if cnt<k:
    print(-1)
else:
    print(cost)

n, K = list(map(int, input().split()))
s = input()
max_n = 104
dp = [[0] * max_n for i in range(max_n)] 
s = "$" + s;
for i in range(n + 1):
  dp[0][i] = 1;

for ln in range(1, n + 1):
  for j in range(1, n + 1):
    dp[ln][j] = dp[ln][j - 1] + dp[ln - 1][j - 1];
    for k in range(j - 1, 0, -1):
      if s[k] == s[j]:
        dp[ln][j] -= dp[ln - 1][k - 1];
        break;
ans = 0;
for ln in range(n, -1, -1):
  cnt = dp[ln][n];
  if (cnt < K):
    ans += (cnt * (n - ln));
    K -= cnt;
  else:
    ans += (K * (n - ln));
    K = 0;
    break;
if (K != 0):
  print(-1)
else:
  print(ans)



def super_solve(n, k, s):
	last = []
	for i in range (0, 256):
		last.append(0)
	dp = []
	for i in range (0, 105):
		tmp = []
		for j in range (0, 105):
			tmp.append(0)
		dp.append( tmp )
	
	now = []
	for i in range (0, 105):
		tmp = []
		for j in range (0, 105):
			tmp.append(0)
		now.append( tmp )

	dp[0][0] = 1
	now[0][0] = 1
	for i in range (1, n + 1):
		c = ord(s[i])
		for j in range (0, n + 1):
			dp[i][j] += dp[i-1][j]
		for j in range (1, n + 1):
			dp[i][j] += dp[i-1][j-1]
		if last[c] > 0:
			for j in range (1, n + 1):
				dp[i][j] -= dp[ last[c] - 1 ][j - 1]
		for j in range (0, n + 1):
			now[i][j] = dp[i][j] - dp[i-1][j]
		last[c] = i



	cost = 0
	baki = k
	j = n
	while( j >= 0 ):
		for i in range (0, n + 1):
			cur = now[i][j]
			my = min(baki, cur)
			cost += my * j
			baki -= my
		j -= 1

	ret = k * n - cost
	if baki > 0:
		ret = -1
	return ret

def main():
	line = input()
	line = line.split(' ')
	n = int(line[0])
	k = int(line[1])
	tmp = input()
	s = []
	s.append(0)
	for i in range (0, n):
		s.append( tmp[i] )
	ret = super_solve(n, k, s)
	print (ret)


def __starting_point():
  main()
__starting_point()

n, d = list(map(int,input().split()))
s = input()
t = [[-1 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if j == i:
			t[i][j] = 1
		else:
			t[i][j] = 0
jes = [0] * 300
for i in range(1, n + 1):
	jes[ord(s[i - 1])] = 1
	t[i][1] = sum(jes)
for j in range(2, n + 1):
	ind = [-1] * 300
	ind[ord(s[j - 1])] = j - 1
	#obliczamy t[j + 1][j], t[j + 2][j], ...
	for i in range(j + 1, n + 1):
		if ind[ord(s[i - 1])] == -1:
			t[i][j] = t[i - 1][j] + t[i-1][j-1] 
		else:
			t[i][j] = t[i - 1][j] + t[i - 1][j - 1] - t[ind[ord(s[i-1])]][j - 1]
		ind[ord(s[i - 1])] = i - 1
#t[n][1], t[n][2], ..., t[n][n]
rozne = [t[n][i] for i in range(1, n + 1)]
rozne.reverse()
roz = rozne + [1]
dupa = 0
wyn = 0
for i in range(n + 1):
	if dupa < d:
		k = min(roz[i], (d-dupa))
		dupa += k
		wyn += k * i
	else:
		break
if dupa >= d:
	print(wyn)
else:
	print(-1)


n, kk = list(map(int, input().split()))
s = '@'+input()
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(i, n+1):
        tag = [True]*26
        for k in range(j, n+1):
            idx = ord(s[k])-ord('a')
            if tag[idx]:
                dp[i][k] += dp[i-1][j-1]
                tag[idx] = False
ans = 0
# print(dp)
for i in range(n, -1, -1):
    # print(ans,k,i)
    tmp = sum(dp[i])
    if kk > tmp:
        kk -= tmp
        ans += (n-i)*tmp
    else:
        ans += kk*(n-i)
        kk = 0
        break
if kk > 0:
    ans = -1
print(ans)


n,setsize=list(map(int,input().split()))
s=input()
count = [[0 for j in range(n+1)] for i in range(n+1)]
for i in range(n):
	j = i-1
	while(j>=0):
		for k in range(1,n):
			count[i][k+1] += count[j][k]
		if(s[j]==s[i]):
			break
		j-=1
	if(j==-1):
		count[i][1]+=1
# print(count)
cost = 0
count[0][0]=1
for l in range(n,-1,-1):
	if(setsize==0):
		break
	ct = 0
	localcost = n - l
	for i in range(n):
		ct += count[i][l]
	minct = min(setsize,ct)
	setsize-=minct
	# print("for k=",setsize,"l=",l,";minct=",minct,";localcost=",localcost)
	cost += (minct*localcost)
if(setsize==0):
	print(cost)
else:
	print(-1)

from sys import stdout, stdin

n, kk = list(map(int, stdin.readline().split()))
s = stdin.readline().strip()
s += "$"
n = n+1

dp = [[0 for i in range(n)] for j in range(n)]
p = 10**15+5
for i in range(n):
    dp[i][0] = 1
for end in range(n):
    for length in range(1, n):
        seen = []
        ans = 0
        for k in range(end-1, -1, -1):
            if s[k] not in seen:
                seen.append(s[k])
                ans += dp[k][length-1]
                ans %= p
        dp[end][length] = ans

totals = [dp[n-1][length] for length in range(n)]
#print(totals)

ans = 0
idx = n-1
while idx >= 0 and kk > 0:
    ans += min(totals[idx], kk)*(n-1-idx)
    kk -= totals[idx]
    idx -= 1

if kk <= 0:
    stdout.write(str(ans) +"\n")
else:
    print(-1)



from string import ascii_lowercase

n, k = map(int, input().split())
s = input()

todo = [1] + ([0] * n)
dp = {letter: [0] * (n + 1) for letter in ascii_lowercase}
for letter in s:
    prev = dp[letter]
    dp[letter] = [0] + todo[:n]
    todo = [a - b + c for a, b, c in zip(todo, prev, dp[letter])]

answer = 0
for cost, amt in enumerate(todo[::-1]):
    if k > amt:
        k -= amt
        answer += amt * cost
    else:
        answer += k * cost
        k = 0
        break
print(-1 if k else answer)

import sys
input = sys.stdin.readline
import bisect
n,k=map(int,input().split())
s=input()
Next=[[float("inf")]*(26) for _ in range(n+1)]
for i in reversed(range(n)):
  for j in range(26):
    Next[i][j]=Next[i+1][j]
  Next[i][ord(s[i])-97]=i
DP=[[0]*(n+1) for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  for j in range(26):
    nxt=Next[i][j]
    for l in range(n):
      if nxt<float("inf"):
        DP[nxt+1][l+1]+=DP[i][l]
Ans=[0]*(n+1)
for i in range(n+1):
  for j in range(n+1):
    Ans[n-j]+=DP[i][j]
Ans2=[0]
for i in range(n+1):
  Ans2.append(Ans2[-1]+Ans[i])
if Ans2[-1]<k:
  print(-1)
else:
  ind=bisect.bisect_left(Ans2,k)
  ans,num=0,0
  for i in range(ind-1):
    ans+=i*Ans[i]
    num+=Ans[i]
  ans+=(ind-1)*(k-num)
  print(ans)

n, k = map(int, input().split())
s = input()
dp = [[0] * 102 for i in range(102)]
dp1 = [[0] * 102  for i in range(30)]

for i in range(0, n + 1):
    dp[i][0] = 1
for i in range(1, n + 1):
    nm = ord(s[i - 1]) - ord('a')
    for le in range(1, i + 1):
        dp[i][le] = dp[i - 1][le] + dp[i - 1][le - 1]
        dp[i][le] -= dp1[nm][le]
    for le in range(1, i + 1):
        dp1[nm][le] += (dp[i][le] - dp[i - 1][le])
        
    
ans = 0
for le in range(n, -1, -1):
    if k == 0:
        break
    x = min(dp[n][le], k)
    ans += (n - le) * x
    k -= x
if k != 0:
    print(-1)
else:
    print(ans)

import math
n, k = map(int, input().split())
# print(n, k)
dp = [[0]*102 for i in range(102)]
# print(len(dp))
s = input()
last = [-1] * 26
for i in range(0, 101):
    dp[i][0] = 1

for i in range(1, n+1):
	for j in range(1, n+1):
		ch = s[i-1]
		dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
		sub = last[ord(ch)-ord('a')]
		if sub == -1:
			continue
		sub -= 1
		dp[i][j] -= dp[sub][j-1]
	last[ord(ch)-ord('a')] = i

ans = int(0)

for i in range(n, -1, -1):# Need to consider empty subsequence too
    if dp[n][i] >= k:
        # print(i, k)
        ans += (k) * (n - i)
        k = 0
    elif (k > 0):
        k -= dp[n][i]
        ans += (n - i) * dp[n][i]
    else:
        break
if k > 0:
    ans = -1
print(ans)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# File              : H.py
# Author            : JCHRYS <jchrys@me.com>
# Date              : 30.08.2019
# Last Modified Date: 30.08.2019
# Last Modified By  : JCHRYS <jchrys@me.com>
class const:
    size = 26; # size of lowercase alphabet

n, k = list(map(int, input().split()));
s = input();

maxpos = [[-1 for _ in range(const.size)] for _ in range(n)];

for i in range(n):
    for j in range(const.size):
        if i > 0:
            maxpos[i][j] = maxpos[i - 1][j]
    maxpos[i][ord(s[i]) - ord('a')] = i

#print(*[row for row in maxpos], sep="\n")
dp = [[0 for _ in range(n + 1)] for _ in range(n)];

for i in range(n):
    dp[i][1] = 1

for length in range(2, n):
    for endswith in range(1, n):
        for before in range(const.size):
            if maxpos[endswith - 1][before] != -1:
                dp[endswith][length] = dp[endswith][length] + dp[maxpos[endswith - 1][before]][length - 1];


#print(*[row for row in dp], sep="\n")
k -= 1;
ans = 0;
for length in range(n-1, 0, -1):
    temp = 0;
    for i in range(const.size):
        if (maxpos[n-1][i] != -1):
            temp += dp[maxpos[n-1][i]][length];
    
    if temp >= k:
        ans += k * (n - length);
        k = 0;
        break;
    else:
        k -= temp;
        ans += temp * (n-length);
  

if (k == 1):
    ans += n;
    k-=1

if k > 0:
    print(-1)
    return
print(ans)






def subsequences_of_length(s):
    n = len(s)

    alphabet = "abcdefghijklmnopqrstuvwxyz"
    to_int = {}
    for i, char in enumerate(alphabet):
        to_int[char] = i

    next_i = [[n] * len(alphabet) for i in range(n + 1)]
    for i in reversed(range(n)):
        for j, char in enumerate(alphabet):
            next_i[i][j] = next_i[i+1][j]
        next_i[i][to_int[s[i]]] = i

    dp = [[0] * (n + 1) for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for k in range(n):
            for j in range(26):
                if next_i[i][j] >= n:
                    continue
                dp[k+1][next_i[i][j] + 1] += dp[k][i]

    ans = [sum(dp[i]) for i in range(n + 1)]
    return ans


n, k = map(int, input().split())
s = input()
ans_len = subsequences_of_length(s)

ans_cnt = 0
ans = 0
for length in reversed(range(len(ans_len))):
    cnt = ans_len[length]
    if ans_cnt + cnt <= k:
        ans_cnt += cnt
        ans += cnt * (n - length)
    else:
        ans += (k - ans_cnt) * (n - length)
        ans_cnt = k
if ans_cnt != k:
    print(-1)
else:
    print(ans)

n, k = list(map(int, input().split()))
s = input()
last = [[-1 for i in range(26)] for j in range(n)]
for i in range(n):
    for j in range(26):
        if i != 0:
            last[i][j] = last[i-1][j]
    last[i][ord(s[i])-ord('a')] = i
dp = [[0 for i in range(n+1)] for j in range(n)]
for i in range(n):
    dp[i][1] = 1
for len in range(2, n+1):
    for i in range(1, n):
        for j in range(26):
            if last[i-1][j] != -1:
                dp[i][len] += dp[last[i-1][j]][len-1]
ans = 0
for len in range(n, 0, -1):
    cnt = 0
    for j in range(26):
        if last[n-1][j] != -1:
            cnt += dp[last[n-1][j]][len]
    if cnt >= k:
        ans += k*(n-len)
        k = 0
        break
    else:
        ans += cnt*(n-len)
        k -= cnt
if k == 1:
    ans += n
    k = 0
if k > 0:
    print(-1)
else:
    print(ans)