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, k \le 100$) — 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:
import sys
import itertools

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

size = 0
cost = 0
cur_set = set()
cur_set.add(string)
for i in range(len_string, -1, -1):
    cur_size = len(cur_set)
    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
    
    new_set = set()
    for substr in cur_set:
        for i in range(len(substr)):
            new_set.add(substr[:i]+substr[(i+1):])
    cur_set = new_set

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


import queue

n, k = [int(el) for el in input().split()]
s = input()


def sol_e(line, set_size):
    unique_set = {line}
    cost = 0
    lines_queue = queue.Queue()
    lines_queue.put(line)
    cur_set_size = 1
    while cur_set_size < set_size:
        cur_line = lines_queue.get()
        for index in range(len(cur_line)):
            new_line = cur_line[:index]+cur_line[(index+1):]
            if new_line not in unique_set:
                unique_set.add(new_line)
                cost += len(line)-len(new_line)
                cur_set_size += 1
                lines_queue.put(new_line)
                if cur_set_size == set_size:
                    return cost
        if lines_queue.empty():
            return -1
    return cost


print(sol_e(s, k))


n, k = list(map(int, input().split()))
s = input()
a = set()
k -= 1
q = [s]
i = 0
ans = 0
while i < len(q) and k > 0:
    for j in range(len(q[i])):
        new = q[i][:j] + q[i][j + 1:]
        if new not in a:
            a.add(new)
            q.append(new)
            ans += n - len(q[i]) + 1
            k -= 1
            if k == 0:
                print(ans)
                return
    i += 1
if k == 0:
    print(ans)
else:
    print(-1)


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)


from queue import Queue
stack = Queue()

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

k -= 1
a = set()
answer = 0

stack.put(list(s))

while not stack.empty():
	now = stack.get_nowait()
	new = now[:]
	can = []
	for i in range(len(now)):
		if k:
			new[i] = ''
			word = ''.join(new)
			if word not in a:
				a.add(word)
				answer += n - len(word)
				can.append(word)
				k -= 1

		new[i] = now[i]
	if k:
		for word in can:
			stack.put(list(word))

if k > 0:
	print(-1)
else:
	print(answer)


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)



def __starting_point():
    n, k = list(map(int, input().split()))
    aa = list(input())
    st = {"".join(aa)}
    arr = [aa]
    w = 0
    c = 0
    cst = 0
    while len(arr) < k and w < len(arr):
        wrd = arr[w][:c] + arr[w][c + 1:]
        wrds = "".join(wrd)
        if wrds not in st:
            st.add(wrds)
            arr.append(wrd)
            cst += n - len(wrd)

        c += 1
        if c >= len(arr[w]):
            c = 0
            w += 1

    if len(arr) < k:
        print(-1)
    else:
        print(cst)

__starting_point()

arr = input()
N,K = [int(num) for num in arr.split(' ')]

string = input()

seq = [string]
record = {}
record[string] = 1
count = 1


while seq and count<=105:
    gen_d = seq.pop(0)
    #print(gen_d)
    for k in range(len(gen_d)):
        r = gen_d[:k] + gen_d[(k+1):]
        if r not in record:
            record[r] = 1
            seq.append(r)
            count += 1

record[''] = 1

G = []
for s in record:
    G.append([N-len(s),s])

G.sort()
#print(G)
res = 0
if len(G)<K:
    print(-1)
else:
    for i in range(K):
        res += G[i][0]
    print(res)

from collections import deque
n, k = list(map(int, input().split()))
s = input()
que = deque()
que.append(s)
d = {}
num = 0
cost = 0
while que:
    q = que.popleft()
    if q not in d:
        cost += n - len(q)
        num += 1
        if num == k:
            print(cost)
            return
        d[q] = 1
        for j in range(len(q)):
            t = q[:j] + q[j + 1:]
            if t not in d:
                que.append(t)

print(-1)



# @author 

import sys

class ESubsequencesEasyVersion:
    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 = ESubsequencesEasyVersion()
input = sys.stdin.readline

solver.solve()


from collections import deque
n,m=list(map(int,input().split()))
s=input()
d=deque([s])
ans=1
an=0
dd={}
while d and ans<m:
    # print(d)
    p=d.popleft()
    dd[p]=1
    k=len(p)
    for i in range(k):
        pp=p[:i] + p[i+1:]
        # print(pp,dd)
        if (pp not in dd):
            an+=(n-(k-1))
            ans+=1
            dd[pp]=1
            d.append(pp)
        if ans==m:
            print(an)
            return
            
    # print(d)
# print(an,ans)    
if ans==m:
    print(an)
else:
    print(-1)
            
        
    
    


import sys
from math import ceil

n, k, = list(map(int, sys.stdin.readline().strip().split()))
s = sys.stdin.readline().strip()

sets = [{s}]
anz = 1
kosten = 0
preis = 0
laenge0 = laenge = len(s)

# one step:
while (anz < k) and laenge:
  laenge -= 1
  kuerzer = []
  for w in sets[-1]:
    w = list(w)
    dazu = [''.join(w[:i] + w[i+1:]) for i in range(len(w))]
    kuerzer += dazu

  sets.append(set(kuerzer))
  anz += len(sets[-1])

if anz<k:
  print(-1)
elif k == 1:
  print(0)
else:
  kosten, bisher = 0, 0
  for preis, it in enumerate(sets[:-1]):
    laenge = len(it)
    bisher += laenge
    kosten += laenge * preis
  kosten += (k-bisher) * (preis+1)
  print(kosten)


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)


from sys import stdin

def subseq(xs, n, m):
    if n > 1:
        sl = subseq(xs[:n//2], n//2, m)
        sr = subseq(xs[n//2:], n - n//2, m)
        return combine(sl, sr, m)
    return xs

def combine(sl, sr, m):
    seq = {s1+s2 for s1 in sl for s2 in sr}.union(sl, sr)
    seql = sorted(seq, key=len, reverse=True) [:m]
    return seql

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

seqs = subseq(s, n, k)
if len(seqs) < k-1:
    print (-1)
else:
    slengths = map((lambda x: n - len(x)), seqs)
    result = sum(slengths)
    if len(seqs) == k-1:
        result += n
    print(result)

n,k=list(map(int,input().split()))
s=input()
st=[set() for i in range(n+1)]
st[n].add(s)
c=1
k-=1
ans=0
for i in range(n,0,-1):
    for w in st[i]:
        for j in range(i):
            st[i-1].add(w[:j]+(w[j+1:] if j!=i-1 else ''))
    sz=len(st[i-1])
    if k<sz:
        ans+=(n-i+1)*k
        k=0
        break
    else:
        ans+=(n-i+1)*sz
        k-=sz
    #print(i,k,ans)
    if k<0:
        break
if k>0:
    print(-1)
else:
    print(ans)
#print(k,ans,st)


N, K = map(int, input().split())
pre = [input()]
ans = 0
k = 1
f = 0
while True:
    if k >= K:
        print(ans)
        break
    if len(pre) == 0:
        print(-1)
        break
    post = []
    for s in pre:
        for i in range(len(s)):
            t = s[:i] + s[i+1:]
            if t not in post:
                k += 1
                post.append(t)
                ans += N-len(t)
                if k >= K:
                    print(ans)
                    f = 1
                    break
        if f:
            break
    if f:
        break
    pre = post

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 = map(int, input().split())
s = input()
a = set()
k -= 1
q = [s]
i = 0
ans = 0
while i < len(q) and k > 0:
    for j in range(len(q[i])):
        new = q[i][:j] + q[i][j + 1:]
        if new not in a:
            a.add(new)
            q.append(new)
            ans += n - len(q[i]) + 1
            k -= 1
            if k == 0:
                print(ans)
                return
    i += 1
if k == 0:
    print(ans)
else:
    print(-1)

from sys import stdin
from collections import deque

n, k = list(map(int, input().split()))
s = input()
que = deque()
que.append(s)
d = {}
num = 0
cost = 0
while que:
    q = que.popleft()
    if q not in d:
        cost += n - len(q)
        num += 1
        if num == k:
            print(cost)
            return
        d[q] = 1
        for j in range(len(q)):
            t = q[:j] + q[j + 1:]
            if t not in d:
                que.append(t)

print(-1)
            
    
        


# your code goes here
n,k=map(int,input().split())
s=input()
c=0
q=[s]
d=set()
ls=0
while q:
	p=q.pop(0)
	if p not in d:
		ls+=1
		c+=(n-len(p))
		if ls==k:
			break
		d.add(p)
		for i in range(len(p)):
			temp=p[:i]+p[i+1:]
			if temp not in d:
				q.append(temp)
			
if ls==k:
	print(c)
else:
	print(-1)

# your code goes here
n,k=map(int,input().split())
s=input()
c=0
q=[s]
d=set()
ls=0
while q:
	p=q.pop(0)
	if p not in d:
		ls+=1
		c+=(n-len(p))
		if ls==k:
			break
		d.add(p)
		for i in range(len(p)):
			temp=p[:i]+p[i+1:]
			if temp not in d:	q.append(temp)
			
if ls==k:	print(c)
else:	print(-1)

from itertools import combinations


def main():
    n, k = list(map(int, input().split()))
    s = input()
    lenf = len
    l_prev = {s}
    curS = 1
    cost = 0
    if k == 1:
        print(0)
        return
    for curlen in range(n - 1, -1, -1):
        l = set()
        for l_elem in l_prev:
            for v in combinations(l_elem, curlen):
                v = ''.join(v)
                if v in l:
                    continue
                l.add(v)
                curS += 1
                cost += n - curlen
                if curS == k:
                    print(cost)
                    return
        l_prev = l
    print(-1)


def __starting_point():
    main()

__starting_point()

n, k = 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)