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: HARD
Tags: Dynamic programming

Graph algorithms

Implementation

Shortest paths
Skill types: Dynamic programming

Starter code:

Solutions:
from sys import stdin, stdout, exit

def price():
	(n, k) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	todo = [s]
	ans = 0
	found = {s: True}
	k -= 1
	while todo and k > 0:
		nexts = []
		for wd in todo:
			for i in range(len(wd)):
				candidate = wd[:i] + wd[i + 1:]
				if candidate not in found:
					nexts.append(candidate)
					found[candidate] = True
					ans += n - len(candidate)
					k -= 1
					if k == 0:
						return ans
		todo = nexts
	if k == 0:
		return ans
	return -1
print(price())


from collections import deque
(n, k) = map(int, input().split())
s = input()
queue = deque([s])
visited = set()
cost = 0
num_of_words = 1
while queue and num_of_words < k:
	new = queue.popleft()
	for i in range(len(new)):
		neigh = new[0:i] + new[i + 1:]
		if neigh not in visited:
			cost += n - len(new) + 1
			num_of_words += 1
			visited.add(neigh)
			queue.append(neigh)
		if num_of_words >= k:
			break
if num_of_words < k:
	print(-1)
else:
	print(cost)


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 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)


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()


alpha = list('abcdefghijklmnopqrstuvwxyz ')

def count_subseq(s):
	n = len(s)
	dp = [[[0] * 27 for i in range(n + 10)] for j in range(n + 10)]
	dp[0][0][26] = 1
	for i in range(1, n + 1):
		st = s[i - 1]
		for j in range(i + 1):
			v = sum((dp[i - 1][j - 1][p] for p in range(27)))
			for last_string in range(27):
				if alpha[last_string] != st:
					dp[i][j][last_string] = dp[i - 1][j][last_string]
				else:
					dp[i][j][last_string] = v
	result = [0] * (n + 1)
	for l in range(n + 1):
		result[l] = sum((dp[n][l][v] for v in range(27)))
	return result

def solution():
	(n, k) = map(int, input().split())
	s = input()
	cntlist = count_subseq(s)
	res = 0
	for length in range(n, -1, -1):
		if k == 0:
			break
		cnt = cntlist[length]
		if cnt >= k:
			res += (n - length) * k
			k = 0
		elif cnt < k:
			res += (n - length) * cnt
			k -= cnt
	if k > 0:
		print(-1)
	else:
		print(res)
	return

def main():
	test = 1
	for i in range(test):
		solution()
	return
main()


from sys import stdin
(n, k) = [int(i) for i in stdin.readline().strip().split()]
s = stdin.readline().strip()

class Subsequences:

	def __init__(self, sequence):
		self._seq = list(sequence)
		self._F = [len(sequence) * [0] for _ in range(len(sequence) + 1)]
		self._calc()

	def _calc(self):
		F = self._F
		size = 0
		for index in range(len(s)):
			F[size][index] = 1
		F[1][0] = 1
		p = {s[0]: 0}
		for i in range(1, len(s)):
			for k in range(1, len(s) + 1):
				if k > i + 1:
					val = 0
				else:
					val = F[k][i - 1] + F[k - 1][i - 1]
					if s[i] in p:
						val -= F[k - 1][p[s[i]] - 1]
				F[k][i] = val
			p[s[i]] = i

	def count(self, size, index=None):
		index = index or len(self._seq) - 1
		return self._F[size][index]
previous_letter_index = {}
found = {}
for (index, letter) in enumerate(s):
	if letter in found:
		previous_letter_index[letter, index] = found[letter]
	found[letter] = index
_subsequences = {}

def subsequences(size, index):
	if (size, index) not in _subsequences:
		if size == 0:
			res = 1
		elif size > index + 1:
			res = 0
		else:
			res = subsequences(size, index - 1) + subsequences(size - 1, index - 1)
			letter = s[index]
			if (letter, index) in previous_letter_index:
				res -= subsequences(size - 1, previous_letter_index[letter, index] - 1)
		_subsequences[size, index] = res
	return _subsequences[size, index]
ss = Subsequences(s)
total_cost = 0
for size in range(len(s), -1, -1):
	if k == 0:
		break
	step_cost = n - size
	sequence_count = subsequences(size, len(s) - 1)
	if sequence_count > k:
		sequence_count = k
	total_cost += step_cost * sequence_count
	k -= sequence_count
if k == 0:
	print(total_cost)
else:
	print(-1)


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)


import sys
from queue import Queue
sys.setrecursionlimit(10000)
(n, k) = map(int, input().split())
s = input().strip()
q = Queue()
q.put(s)
res = {s}
while not q.empty():
	if len(res) == k:
		break
	string = q.get()
	for i in range(len(string)):
		new_string = string[:i] + string[i + 1:]
		if new_string not in res:
			res.add(new_string)
			q.put(new_string)
			if len(res) == k:
				break
if len(res) != k:
	print(-1)
	exit()
print(n * k - sum((len(string) for string in res)))


def count_subsequences_of_length(s):
	n = len(s)
	alphabet = list(set(list(s)))
	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 j in range(n):
		for i in range(n):
			for k in range(len(alphabet)):
				if next_i[j][k] >= n:
					continue
				dp[i + 1][next_i[j][k] + 1] += dp[i][j]
	ans = [sum(dp[i]) for i in range(n + 1)]
	return ans
(n, k) = map(int, input().split())
s = input()
ans_len = count_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)


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)
	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()
res = 0
if len(G) < K:
	print(-1)
else:
	for i in range(K):
		res += G[i][0]
	print(res)


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) = map(int, input().split())
S = input()
dp = [[0] * 110 for i in range(110)]
lst = [[0] * 110 for i in range(110)]
for i in range(N + 1):
	dp[i][0] = 1
for k in range(26):
	lst[0][k] = -1
for i in range(N):
	num = ord(S[i]) - ord('a')
	for k in range(26):
		lst[i + 1][k] = lst[i][k]
	lst[i + 1][num] = i
for i in range(N):
	num = ord(S[i]) - ord('a')
	for k in range(1, N + 1):
		dp[i + 1][k] = dp[i][k] + dp[i][k - 1]
		if lst[i][num] != -1:
			dp[i + 1][k] -= dp[lst[i][num]][k - 1]
rem = K
ans = 0
for i in range(0, N + 1):
	k = N - i
	if dp[N][k] >= rem:
		ans += rem * (N - k)
		rem = 0
	else:
		ans += dp[N][k] * (N - k)
		rem -= dp[N][k]
if rem > 0:
	print(-1)
else:
	print(ans)


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


import sys
input = sys.stdin.readline
from collections import deque
(n, k) = map(int, input().split())
s = list(input().rstrip())
vis = set()
dq = deque([''.join(s)])
cnt = 0
score = 0
while dq:
	ss = dq.popleft()
	if ss not in vis:
		score += n - len(ss)
		cnt += 1
		vis.add(ss)
	else:
		continue
	if cnt >= k:
		break
	for i in range(len(ss)):
		nxt = ss[:i] + ss[i + 1:]
		dq.append(''.join(nxt))
if cnt < k:
	print(-1)
else:
	print(score)


from functools import lru_cache

@lru_cache(maxsize=None)
def e(n, l):
	return sum((d(n, l, x) for x in letters))

@lru_cache(maxsize=None)
def d(n, l, c):
	if n < l:
		return 0
	if s[n - 1] != c:
		return d(n - 1, l, c)
	return e(n - 1, l - 1) if l > 1 else 1

def solve(s, n, k):
	cost = 0
	for l in range(n, 0, -1):
		cnt = e(n, l)
		if k > cnt:
			k -= cnt
			cost += cnt * (n - l)
		else:
			return cost + k * (n - l)
	return cost + n if k == 1 else -1
(n, k) = map(int, input().split())
s = input()
letters = set(s)
print(solve(s, n, k))


def solve(n, k, s):
	total_length = 0
	queue = [s]
	ss = set()
	while queue and len(ss) < k:
		s = queue.pop(0)
		if s not in ss:
			ss.add(s)
			total_length += len(s)
			if len(ss) < k:
				for i in range(len(s)):
					temp = s[:i] + s[i + 1:]
					if temp not in ss:
						queue.append(temp)
	if len(ss) < k:
		return -1
	return n * k - total_length
(n, k) = map(int, input().split())
s = input()
print(solve(n, k, s))


import queue

def check(arr, p):
	if p in arr:
		return False
	return True
[n, k] = [int(i) for i in input().split()]
s = input()
L = queue.Queue(maxsize=k + 2)
L.put(s)
ctr = 1
arr = []
ans = 0
org = len(s)
while ctr < k and L.empty() == False:
	x = L.get()
	if len(x) > 1:
		qorg = len(x)
		for g in range(len(x)):
			if ctr == k:
				break
			p = x[:g] + x[g + 1:]
			if check(arr, p):
				arr.append(p)
				ctr += 1
				ans += org - (qorg - 1)
				L.put(p)
if ctr == k:
	print(ans)
elif ctr == k - 1:
	print(ans + org)
else:
	print(-1)


(n, k) = map(int, input().split())
s = str(input())
s1 = ''
sub = [s]
inv = {}
c = 0
kq = 0
while len(sub) > 0:
	tem = sub[0]
	del sub[0]
	if inv.get(tem, 0) == 0:
		inv[tem] = 1
		c += 1
		kq += n - len(tem)
		if c == k:
			break
		for i in range(len(tem)):
			s1 = tem[:i] + tem[i + 1:]
			sub.append(s1)
if c < k:
	kq = -1
print(kq)


from itertools import combinations
(n, k) = map(int, input().split())
s = str(input())

def rSubset(arr, r):
	return set(list(combinations(arr, r)))

def repeat(s):
	l = list(s)
	l2 = []
	for i in range(len(s)):
		if l[i] == str(s[0]):
			l2.append(True)
		else:
			l2.append(False)
	if False in l2:
		return False
	else:
		return True

def test(B):
	if len(B) < k:
		return '-1'
	else:
		B = B[0:k]
		cost = 0
		for x in B:
			cost += n - len(x)
		return cost
master = []
B = {s}
A = set()
for z in range(len(s)):
	if len(master) >= k:
		break
	for x in B:
		A.update(list(rSubset(x, len(x) - 1)))
		if len(A) > k:
			A = list(A)
			A.sort(key=len)
			break
	master += B
	B = A
	A = set()
master.append('')
print(test(master))


(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
	if k < 0:
		break
if k > 0:
	print(-1)
else:
	print(ans)


(n, k) = list(map(int, input().split()))
s = input()
sett = {s}
q = [s]
m = n
while len(q) and len(sett) < k:
	node = q.pop(0)
	for i in range(0, len(node)):
		ss = node[:i] + node[i + 1:]
		if not ss in sett and len(sett) < k:
			q.append(ss)
			sett.add(ss)
			m += len(ss)
print('-1' if len(sett) < k else n * k - m)


from collections import deque
(n, k) = map(int, input().split())
s = input()
myset = set()
myset.add(s)
queue = deque([s])
while len(queue) >= 1 and len(myset) < k:
	stmp = queue.popleft()
	for i in range(len(stmp)):
		stmp1 = stmp[:i] + stmp[i + 1:]
		if stmp1 not in myset:
			myset.add(stmp1)
			queue.append(stmp1)
if len(myset) < k:
	print(-1)
else:
	lst = sorted(list(myset), reverse=True, key=lambda s: len(s))
	ans = 0
	n = len(s)
	for i in range(k):
		ans += n - len(lst[i])
	print(ans)


import sys
(n, k) = map(int, sys.stdin.readline().split(' '))
s = sys.stdin.readline().strip()
lt = [s]
count = 0
flag = False
result = 0
while lt:
	cur_s = lt[0]
	lt.pop(0)
	result += len(s) - len(cur_s)
	count += 1
	if count >= k:
		break
	for i in range(0, len(cur_s)):
		new_s = cur_s[0:i] + cur_s[i + 1:]
		if new_s not in lt:
			lt.append(new_s)
if count < k:
	sys.stdout.write(str(-1) + '\n')
else:
	sys.stdout.write(str(result) + '\n')


(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)


(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

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)


from itertools import combinations

def main():
	(n, k) = 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)
main()


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)


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])]
		num_subsequences_for_this_letter_so_far[val_of_letter(string[i])] = last_num_subsequences_so_far[i + 1]
	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]
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')


def sol(b):
	c = []
	for i in range(len(b)):
		c.append(b[:i] + b[i + 1:])
	return c
s = set()
(n, k) = map(int, input().split())
st = input()
la = n
p = [st]
p = set(p)
while la > 0:
	s = s.union(p)
	r = set()
	fl = 0
	for i in p:
		c = sol(i)
		la = len(c[0])
		r = r.union(set(c))
		if len(s) + len(r) >= k:
			fl = 1
			break
	p = r
	if fl:
		break
ans = 0
s = s.union(p)
if len(s) < k:
	exit(print(-1))
else:
	p = sorted(list(s), reverse=True, key=len)
	for i in range(k):
		ans += n - len(p[i])
	print(ans)


(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)


def main():
	from sys import stdin
	input = stdin.readline
	(n, k) = map(int, input().split())
	s = input()[:-1]
	dp = [[0] * 26 for i in range(n + 1)]
	dp[0][0] = 1
	for ch in s:
		j = ord(ch) - ord('a')
		for i in range(n, 0, -1):
			dp[i][j] = sum(dp[i - 1])
	x = 0
	y = 0
	for i in range(n, -1, -1):
		if x + sum(dp[i]) >= k:
			print(k * n - y - (k - x) * i)
			break
		x += sum(dp[i])
		y += i * sum(dp[i])
	else:
		print(-1)
main()


(n, K) = map(int, input().split())
s = input()
kolvo = 1
res = 0
d = {}
d[0] = []
d[0].append(s)
level = 0
while kolvo < K and level <= n:
	level += 1
	d[level] = []
	for subs in d[level - 1]:
		for j in range(len(subs)):
			subs1 = subs[:j] + subs[j + 1:]
			if subs1 not in d[level]:
				d[level].append(subs1)
				kolvo += 1
				res += level
				if kolvo == K:
					break
		if kolvo == K:
			break
if kolvo < K:
	res = -1
print(res)


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)


from collections import defaultdict
(n, k) = map(int, input().split())
s = input()
last = defaultdict(int)
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 1
dp[1][1] = 1
dp[1][0] = 1
last[s[0]] = 1
for i in range(2, n + 1):
	dp[i][0] = 1
	for j in range(1, i + 1):
		dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
		if last[s[i - 1]] >= 1:
			ind = last[s[i - 1]]
			dp[i][j] -= dp[ind - 1][j - 1]
	last[s[i - 1]] = i
ans = 0
for i in range(n, -1, -1):
	if k <= 0:
		break
	c = min(dp[n][i], k)
	ans += (n - i) * c
	k -= c
if k > 0:
	ans = -1
print(ans)


(n, kk) = 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
for i in range(n, -1, -1):
	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)


from sys import stdin
(n, k) = [int(i) for i in stdin.readline().strip().split()]
s = stdin.readline().strip()

def get_f(s):
	F = [len(s) * [0] for _ in range(len(s) + 1)]
	size = 0
	for index in range(len(s)):
		F[size][index] = 1
	F[1][0] = 1
	p = {s[0]: 0}
	for i in range(1, len(s)):
		for k in range(1, len(s) + 1):
			if k > i + 1:
				val = 0
			else:
				val = F[k][i - 1] + F[k - 1][i - 1]
				if s[i] in p:
					if p[s[i]] - 1 >= 0:
						val -= F[k - 1][p[s[i]] - 1]
					elif p[s[i]] == 0 and k - 1 == 0:
						val -= 1
			F[k][i] = val
		p[s[i]] = i
	return F
_F = get_f(s)

def count(size, index=None):
	return _F[size][index or len(s) - 1]
previous_letter_index = {}
found = {}
for (index, letter) in enumerate(s):
	if letter in found:
		previous_letter_index[letter, index] = found[letter]
	found[letter] = index
_subsequences = {}

def subsequences(size, index):
	if (size, index) not in _subsequences:
		if size == 0:
			res = 1
		elif size > index + 1:
			res = 0
		else:
			res = subsequences(size, index - 1) + subsequences(size - 1, index - 1)
			letter = s[index]
			if (letter, index) in previous_letter_index:
				res -= subsequences(size - 1, previous_letter_index[letter, index] - 1)
		_subsequences[size, index] = res
	return _subsequences[size, index]
total_cost = 0
for size in range(len(s), -1, -1):
	if k == 0:
		break
	step_cost = n - size
	sequence_count = count(size, len(s) - 1)
	if sequence_count > k:
		sequence_count = k
	total_cost += step_cost * sequence_count
	k -= sequence_count
if k == 0:
	print(total_cost)
else:
	print(-1)


import sys
import math
from collections import defaultdict, deque
import heapq
(n, k) = map(int, sys.stdin.readline().split())
ss = sys.stdin.readline()[:-1]
dp = [[0 for _ in range(n + 1)] for i in range(n + 1)]
dp[n][1] = 1
dp[n][0] = 1
dic = defaultdict(list)
for i in range(n):
	dic[ss[i]].append(i + 1)
for i in range(n - 1, 0, -1):
	for j in range(1, n + 1):
		s = 0
		for x in range(i + 1, n + 1):
			s += dp[x][j - 1]
		z = -1
		cnt = 0
		for y in dic[ss[i - 1]]:
			cnt += 1
			if y == i:
				break
		sub = 0
		if len(dic[ss[i - 1]]) > cnt:
			for q in range(cnt, len(dic[ss[i - 1]])):
				sub += dp[dic[ss[i - 1]][q]][j]
		dp[i][j] += s - sub
cost = 0
for i in range(n, -1, -1):
	for j in range(n + 1):
		if dp[j][i] <= k:
			cost += (n - i) * dp[j][i]
			k -= dp[j][i]
		else:
			cost += k * (n - i)
			k = 0
			break
if k != 0:
	print(-1)
else:
	print(cost)


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)
main()


from queue import Queue
(n, k) = map(int, input().split())
s = input()
cost = n
vis = set()
q = Queue()
q.put(s)
vis.add(s)
while not q.empty() and len(vis) < k:
	u = q.get()
	for i in range(len(u)):
		v = u[:i] + u[i + 1:]
		if v not in vis:
			vis.add(v)
			q.put(v)
			cost += len(v)
			if len(vis) == k:
				break
if len(vis) != k:
	print(-1)
else:
	print(n * k - cost)


from collections import deque
(n, k) = map(int, input().split())
s = input()
dp = [0] * (n + 1)
kk = dict()
ct = 0
q = deque()
q.append(s)
while q:
	r = q.popleft()
	dp[len(r)] += 1
	ct += 1
	if ct > k + 10:
		break
	if len(r) > 0:
		for i in range(0, len(r)):
			st = r[:i] + r[i + 1:]
			if kk.get(st) == None:
				kk[st] = 1
				q.append(st)
tot = 0
for i in range(0, len(dp)):
	tot += dp[i]
if tot < k:
	print(-1)
else:
	sumu = 0
	c = 0
	for i in range(n, -1, -1):
		req = min(k - c, dp[i])
		c += req
		sumu += req * (n - i)
		if c >= k:
			break
	print(sumu)


import sys
from itertools import combinations
from functools import lru_cache
from string import ascii_lowercase

@lru_cache()
def e(n, l):
	return sum((d(n, l, x) for x in letters))

@lru_cache()
def d(n, l, c):
	if n < l:
		return 0
	if s[n - 1] != c:
		return d(n - 1, l, c)
	return e(n - 1, l - 1) if l > 1 else 1

def solve(s, k):
	n = len(s)
	cost = 0
	for l in range(n, 0, -1):
		cnt = e(n, l)
		if k > cnt:
			k -= cnt
			cost += cnt * (n - l)
		else:
			cost += k * (n - l)
			k = 0
			break
	if k > 1:
		return -1
	if k == 1:
		cost += n
		k = 0
	return cost
(n, k) = map(int, input().split())
s = input()
letters = set(s)
print(solve(s, k))


from sys import stdout, stdin
(n, kk) = 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)]
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)


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()


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)
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)


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


(n, k) = map(int, input().split())
r = set()
r1 = set()
a = input()
queue = [a]
cost = 0
co = 0
r1.add(a)
while queue:
	ref = queue.pop(0)
	if ref not in r:
		r.add(ref)
		cost += n - len(ref)
		co += 1
	if co == k:
		break
	for i in range(len(ref)):
		y = ref[:i] + ref[i + 1:]
		if y not in r1:
			queue.append(y)
			r1.add(y)
if len(r) < k:
	print(-1)
	exit(0)
print(cost)


[n, k] = [int(i) for i in input().split()]
S = [input()]
l = 0
x = 0
c = 0
while len(S) < k:
	d = k - len(S)
	a = set()
	for i in range(l, len(S)):
		for j in range(0, len(S[i])):
			s = S[i][:j] + S[i][j + 1:]
			if s not in a:
				a.add(s)
				c += x + 1
				d -= 1
				if d == 0:
					break
		if d == 0:
			break
	if a == set():
		c = -1
		break
	x += 1
	l = len(S)
	S += list(a)
print(c)


import math
(n, k) = map(int, input().split())
dp = [[0] * 102 for i in range(102)]
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):
	if dp[n][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)


(n, k) = input().split(' ')
n = int(n)
k = int(k)
s = input()
s = '-' + s
dp = [[0 for i in range(110)] for j in range(110)]
added = [[0 for i in range(110)] for j in range(110)]
lst = [0 for i in range(310)]
lstAdded = [0 for i in range(310)]
for i in range(0, 110):
	dp[0][i] = 1
vec = list()
st = set()
for i in range(1, n + 1):
	st.add(s[i])
	dp[1][i] = len(st)
vec.append(1)
vec.append(dp[1][n])
for t in range(2, n + 1):
	for i in range(310):
		lst[i] = 0
		lstAdded[i] = 0
	for i in range(1, n + 1):
		dp[t][i] = dp[t - 1][i - 1] + dp[t][i - 1] - lstAdded[ord(s[i])]
		lstAdded[ord(s[i])] += dp[t][i] - dp[t][i - 1]
		added[t][i] = dp[t][i] - dp[t][i - 1]
		lst[ord(s[i])] = i
	vec.append(dp[t][n])
ans = 0
qnt = 0
while k > 0 and len(vec):
	now = vec.pop()
	use = min(k, now)
	k = k - use
	ans += qnt * use
	qnt += 1
if k == 0:
	print(ans)
else:
	print(-1)


from queue import Queue
stack = Queue()
(n, k) = 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)


def func(n, k, s):
	x = [s]
	cost = 0
	while len(x) < k:
		for string in x:
			l = len(string)
			for j in range(l):
				t = string[:j] + string[j + 1:]
				if t == '' and t in x:
					return -1
				if t not in x:
					x.append(t)
					cost += n - len(t)
					if len(x) >= k:
						return cost
	return cost
a = [int(i) for i in input().split()]
n = a[0]
k = a[1]
s = str(input())
print(func(n, k, s))


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:
	p = d.popleft()
	dd[p] = 1
	k = len(p)
	for i in range(k):
		pp = p[:i] + p[i + 1:]
		if pp not in dd:
			an += n - (k - 1)
			ans += 1
			dd[pp] = 1
			d.append(pp)
		if ans == m:
			print(an)
			return
if ans == m:
	print(an)
else:
	print(-1)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
sys.setrecursionlimit(300000)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class BinaryTrie:

	class Node:

		def __init__(self, bit: bool=False):
			self.bit = bit
			self.children = []
			self.count = 0
			self.counter = 1

	def __init__(self, size):
		self.root = BinaryTrie.Node()
		self.size = size

	def convert(self, key):
		bits = []
		if isinstance(key, int):
			key = bin(key)[2:]
		if isinstance(key, str):
			for i in range(self.size - len(key)):
				bits += [False]
			for i in key:
				if i == '0':
					bits += [False]
				else:
					bits += [True]
		else:
			return list(key)
		return bits

	def add(self, key):
		node = self.root
		bits = self.convert(key)
		for bit in bits:
			found_in_child = False
			for child in node.children:
				if child.bit == bit:
					child.counter += 1
					node = child
					found_in_child = True
					break
			if not found_in_child:
				new_node = BinaryTrie.Node(bit)
				node.children.append(new_node)
				node = new_node
		node.count += 1

	def remove(self, key):
		node = self.root
		bits = self.convert(key)
		nodelist = [node]
		for bit in bits:
			for child in node.children:
				if child.bit == bit:
					node = child
					node.counter -= 1
					nodelist.append(node)
					break
		node.count -= 1
		if not node.children and (not node.count):
			for i in range(len(nodelist) - 2, -1, -1):
				nodelist[i].children.remove(nodelist[i + 1])
				if nodelist[i].children or nodelist[i].count:
					break

	def query(self, prefix, root=None):
		if not root:
			root = self.root
		node = root
		if not root.children:
			return 0
		for bit in prefix:
			bit_not_found = True
			for child in node.children:
				if child.bit == bit:
					bit_not_found = False
					node = child
					break
			if bit_not_found:
				return 0
		return node

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.data = 0
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key, val):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
			pCrawl.data += val
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		c = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None

	def present(self, key):
		ans = 0
		pCrawl = self.root
		length = len(key)
		c = 0
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
			ans += pCrawl.data
		if pCrawl != None:
			return ans
		return -1
(n, k) = map(int, input().split())
s = input()
last = defaultdict(int)
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
dp[0][0] = 1
dp[1][1] = 1
dp[1][0] = 1
last[s[0]] = 1
for i in range(2, n + 1):
	dp[i][0] = 1
	for j in range(1, i + 1):
		dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
		if last[s[i - 1]] >= 1:
			ind = last[s[i - 1]]
			dp[i][j] -= dp[ind - 1][j - 1]
	last[s[i - 1]] = i
ans = 0
for i in range(n, -1, -1):
	if k <= 0:
		break
	c = min(dp[n][i], k)
	ans += (n - i) * c
	k -= c
if k > 0:
	ans = -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)


ls = list(map(int, input().split()))
s = input()
q = [s]
(n, k) = (ls[0], ls[1])
l = set()
c = 0
cost = 0
while len(q) != 0:
	p = q.pop(0)
	if p not in l:
		l.add(p)
		cost = cost + len(s) - len(p)
		if len(l) == k:
			c = 1
			break
		for i in range(len(p)):
			t = p[:i] + p[i + 1:]
			if t not in l:
				q.append(t)
if c == 1:
	print(str(cost))
else:
	print(str(-1))


from collections import deque

def bfs(s):
	q = deque()
	q.append(s)
	visited = set()
	visited.add(s)
	ans = 0
	while q and len(visited) < k:
		v_curr = q.popleft()
		for i in range(len(v_curr)):
			vt = v_curr[:i] + v_curr[i + 1:]
			if vt not in visited and len(visited) + 1 <= k:
				visited.add(vt)
				q.append(vt)
				ans += n - len(vt)
	return ans if len(visited) == k else -1
(n, k) = map(int, input().split())
s = input()
cost = 0
print(bfs(s))


from collections import defaultdict

def solve(s, k):
	dp = defaultdict(int)
	dp[-1, -1] = 1
	n = len(s)
	last = {}
	for i in range(n):
		dp[i, -1] = 1
		for j in range(i + 1):
			dp[i, j] = dp[i - 1, j - 1] + dp[i - 1, j]
			if s[i] in last:
				dp[i, j] -= dp[last[s[i]] - 1, j - 1]
		last[s[i]] = i
	cost = 0
	for i in reversed(range(-1, n)):
		cost += min(dp[n - 1, i], k) * (n - 1 - i)
		k -= dp[n - 1, i]
		if k <= 0:
			return cost
	return -1
(n, k) = list(map(int, input().split()))
s = input()
print(solve(s, k))


iarr = list(map(int, input().split()))
n = iarr[0]
k = iarr[1]
s = input()
arr = []
arr.append(s)
ans = 0
ii = 0
flagg = 0
while True:
	if flagg == 1:
		break
	if arr[ii] == '':
		break
	l = len(arr[ii])
	curcost = n - l + 1
	for i in range(l):
		ss = arr[ii][:i] + arr[ii][i + 1:]
		ll = len(arr)
		flag = True
		for j in range(ll):
			flag = flag and ss != arr[j]
		if len(arr) == k:
			flagg = 1
			break
		if flag:
			arr.append(ss)
			ans += curcost
	ii += 1
if len(arr) != k:
	print(-1)
else:
	print(ans)


from queue import Queue
(n, k) = [int(x) for x in input().split()]
s = input()
if k == 1:
	print(0)
	exit()
k = k - 1
q = Queue()
q.put((s, 0))
added = 1
count = 0
answer = 0
found = False
st = set()
while not found and (not q.empty()):
	el = q.get()
	e = el[0]
	for i in range(len(e)):
		subs = e[0:i] + e[i + 1:]
		if subs in st:
			continue
		st.add(subs)
		q.put((subs, 1 + el[1]))
		answer = answer + el[1] + 1
		count += 1
		if count == k:
			found = True
			print(answer)
			break
if not found:
	print(-1)


(n, k) = map(int, input().split())
targets = [input()]
ans = 0
cur = 1
depth = 0
if cur >= k:
	print(ans)
	exit()
while depth <= n:
	depth += 1
	next_target = []
	for target in targets:
		for i in range(len(target)):
			check = target[:i] + target[i + 1:]
			if check in next_target:
				continue
			next_target.append(target[:i] + target[i + 1:])
			ans += depth
			cur += 1
			if cur >= k:
				print(ans)
				exit()
	targets = next_target
print(-1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def c(chr):
	return ord(chr) - ord('a')

def main():
	(n, k) = RL()
	s = input()
	dp = [[0] * (n + 1) for i in range(n + 1)]
	rec = [-1] * 26
	pre = [-1] * n
	for i in range(n + 1):
		dp[i][0] = 1
	for i in range(n):
		now = c(s[i])
		pre[i] = rec[now]
		rec[now] = i
	for i in range(1, n + 1):
		for j in range(1, i + 1):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
			if pre[i - 1] != -1:
				dp[i][j] -= dp[pre[i - 1]][j - 1]
	res = 0
	for j in range(n, -1, -1):
		if k:
			num = min(k, dp[-1][j])
			k -= num
			res += (n - j) * num
	print(res if k == 0 else -1)
main()


import sys
from collections import defaultdict
(n, k) = map(int, input().split())
s = input()
b = []
for j in s:
	b.append(j)
dp = [[0 for i in range(n + 1)] for j in range(n)]
last = defaultdict(lambda : 0)
dp[0][0] = 1
dp[0][1] = 1
last[b[0], 0] = 1
last[b[0], 1] = 1
for i in range(1, n):
	dp[i][0] = 1
	for j in range(1, n + 1):
		dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - last[b[i], j]
		last[b[i], j] = dp[i - 1][j - 1]
s = 0
res = 0
if sum(dp[-1]) < k:
	print(-1)
	sys.exit()
j = n
while j >= 0:
	if s + dp[-1][j] < k:
		s += dp[-1][j]
		res += dp[-1][j] * (n - j)
	else:
		res += (k - s) * (n - j)
		break
	j += -1
print(res)


(n, k) = map(int, input().split())
dict1 = {}
sumx = 0
ans = 1
s = str(input())
arr = [s]
flag = 0
dict1[s] = 1
while flag == 0 and len(dict1) < k:
	arr1 = []
	for i in range(len(arr)):
		for j in range(len(arr[i])):
			try:
				dict1[arr[i][:j] + arr[i][j + 1:]] += 1
			except:
				KeyError
				dict1[arr[i][:j] + arr[i][j + 1:]] = 1
				arr1.append(arr[i][:j] + arr[i][j + 1:])
				ans += 1
				if len(dict1) == k or ans == k:
					flag = 1
					break
		if len(dict1) == k or ans == k:
			flag = 1
			break
	if len(arr1) == 0:
		flag = 2
		break
	arr = arr1
if flag == 2:
	print(-1)
else:
	sumx = 0
	for i in dict1.keys():
		sumx += n - len(i)
	print(sumx)


(n, k) = map(int, input().split())
s = '{' + input()
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
oa = ord('a')
for i in range(1, n + 1):
	for j in range(1, n + 1):
		hold = [0] * 30
		for l in range(0, i):
			let = ord(s[l]) - oa
			dp[i][j] += dp[l][j - 1] - hold[let]
			hold[let] = dp[l][j - 1]
tot = 0
for i in range(n, -1, -1):
	cost = n - i
	dpsum = 0
	hold = [0] * 30
	for j in range(0, n + 1):
		let = ord(s[j]) - oa
		dpsum += dp[j][i] - hold[let]
		hold[let] = dp[j][i]
	sub = min(k, dpsum)
	tot += sub * cost
	k -= sub
if k > 0:
	print(-1)
else:
	print(tot)


(n, k) = map(int, input().split())
s = input()
from collections import defaultdict
cost = 0
vis = set()
q = [s]
cnt = 0
while q:
	t = q.pop(0)
	if t not in vis:
		vis.add(t)
		cnt += 1
		cost += n - len(t)
		if cnt == k:
			break
		for i in range(len(t)):
			curr = t[:i] + t[i + 1:]
			if curr not in vis:
				q.append(curr)
if cnt == k:
	print(cost)
else:
	print(-1)


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(src, S, K):
	from collections import deque
	if K == 1:
		return set([src])
	que = deque([src])
	res = set()
	res.add(src)
	while que:
		s = que.popleft()
		for i in range(len(s)):
			t = s[:i] + s[i + 1:]
			if t in res:
				continue
			que.append(t)
			res.add(t)
			if len(res) == K:
				return res
	return res
(N, K) = MAP()
S = input()
res = bfs(S, S, K)
if len(res) < K:
	print(-1)
else:
	ans = 0
	for s in res:
		ans += N - len(s)
	print(ans)


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


import sys

def eprint(*args, **kwargs):
	if __debug__:
		print(*args, file=sys.stderr, **kwargs)

def calculate_res(visit, n):
	return n * len(visit) - sum([len(x) for x in visit])

def traverse(s, k):
	_que = []
	visit = set([])
	_que.append(s)
	visit.add(s)
	if len(visit) == k:
		return calculate_res(visit, len(s))
	while len(_que) > 0:
		cur = _que.pop(0)
		for i in range(len(cur)):
			adj_s = cur[0:i] + cur[i + 1:len(cur)]
			if adj_s not in visit:
				_que.append(adj_s)
				visit.add(adj_s)
				if len(visit) == k:
					return calculate_res(visit, len(s))
	return -1
(n, k) = map(int, input().split(' '))
s = input()
print(traverse(s, k))


(n, k) = map(int, input().split())
str = str(input())
q = [str]
ans = 0
ma = {}
while len(q) != 0 and k > 1:
	s = q[0]
	q.remove(q[0])
	for i in range(len(s)):
		ss = s
		s1 = ss[0:i]
		s2 = ss[i + 1:]
		ss = s1 + s2
		if ss not in ma.keys():
			ma[ss] = 1
			k -= 1
			ans += n - len(ss)
			q.append(ss)
			if k == 1:
				break
if k == 1:
	print(ans)
else:
	print(-1)


[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)


import sys
input = sys.stdin.readline
(n, W) = 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]
HLIST = [0] * (n + 1)
for i in range(n + 1):
	for j in range(n + 1):
		HLIST[j] += DP[i][j]
ANS = 0
for i in range(n, -1, -1):
	if W > HLIST[i]:
		ANS += (n - i) * HLIST[i]
		W -= HLIST[i]
	else:
		ANS += W * (n - i)
		print(ANS)
		sys.exit()
else:
	print(-1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def solution(A, k):
	N = len(A)
	if N < k or N < 1 or k < 1:
		return 0
	if N == k:
		return 1
	v1 = [0] * N
	v2 = [0] * N
	v3 = [0] * N
	v2[N - 1] = 1
	v3[A[N - 1] - 1] = 1
	for i in range(N - 2, -1, -1):
		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] * N
		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]
		for i in range(len(v1)):
			v2[i] = v1[i]
	return v2[0]

def solve(a, n, k):
	v = a
	return solution(v, k)
from collections import defaultdict
(n, k) = map(int, input().split())
string1 = [ord(k) for k in input()]
ans = []
vv = set(string1)
vv = list(vv)
vv.sort()
dmap = defaultdict(int)
for s in range(len(vv)):
	dmap[vv[s]] = s + 1
string1 = [dmap[k] for k in string1]
for s in range(1, n + 1):
	ans.append(solve(string1, n, s))
ret = 0
for s in range(n - 1, -1, -1):
	if k >= ans[s]:
		k -= ans[s]
		ret += (n - (s + 1)) * ans[s]
	else:
		ret += (n - (s + 1)) * k
		k = 0
		break
if k == 0:
	print(ret)
elif k == 1:
	print(ret + n)
else:
	print(-1)


(n, k) = map(int, input().split())
s = input()
pos = [-1] * 26
lst = []
for i in range(0, len(s)):
	pos[ord(s[i]) - 97] = i
	h = []
	for j in range(26):
		h.append(pos[j])
	lst.append(h)
dp = []
for i in range(n):
	h = []
	for j in range(n + 1):
		h.append(0)
	dp.append(h)
for i in range(n):
	dp[i][1] = 1
for j in range(2, n + 1):
	for i in range(1, n):
		for e in range(26):
			if lst[i - 1][e] != -1:
				dp[i][j] = dp[i][j] + dp[lst[i - 1][e]][j - 1]
ans = 0
for j in range(n, 0, -1):
	c = 0
	for e in range(26):
		if lst[n - 1][e] != -1:
			c += dp[lst[n - 1][e]][j]
	if k - c >= 0:
		ans += c * (n - j)
		k -= c
	else:
		req = k
		ans += req * (n - j)
		k -= req
		break
if k == 1:
	ans += n
	k -= 1
if k > 0:
	print(-1)
else:
	print(ans)


inp = input()
inp = inp.split(' ')
n = int(inp[0])
k = int(inp[1])
cost = 0
inp1 = input()
l = []
l.append(inp1)
check = 1
b = False
for i in range(1, n + 1):
	l1 = []
	for word in l:
		for j in range(len(word)):
			l1.append(word[0:j] + word[j + 1:len(word)])
	l1 = list(set(l1))
	l = l1
	if check + len(l1) < k:
		cost += len(l1) * i
		check = check + len(l1)
	else:
		b = True
		cost += (k - check) * i
		break
if b:
	print(cost)
else:
	print(-1)


def solve(n, k, s):
	set = {}
	queue = []
	ans = 0
	queue.append(s)
	set[s] = 1
	while len(queue) > 0 and len(set) < k:
		curr = queue.pop(0)
		for i in range(len(curr)):
			newS = curr[:i] + curr[i + 1:]
			if newS not in set and len(set) + 1 <= k:
				set[newS] = 1
				ans += n - len(newS)
				queue.append(newS)
	print(ans if len(set) == k else -1)

def main():
	(n, k) = map(int, input().split())
	s = input()
	solve(n, k, s)
main()


line = input()
need = int(line.split(' ')[1]) - 1
n = int(line.split(' ')[0])
s = input()
if need == 0:
	print(0)
else:
	queue = [s]
	d = {}
	(head, tail, ans) = (0, 1, 0)
	solve = False
	while head < tail and (not solve):
		top = queue[head]
		cost = len(top) - 1
		for (idx, c) in enumerate(top):
			new = ''.join([top[:idx], top[idx + 1:]])
			h = new.__hash__()
			if not d.get(h):
				d[h] = 1
				queue.append(new)
				tail += 1
				ans += n - cost
				need -= 1
				if need == 0:
					solve = True
					break
		head += 1
	if not solve:
		print('-1')
	else:
		print(ans)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
s = ['?'] + list(input().rstrip())
dp = []
dp0 = [0] * (n + 1)
dp0[0] = 1
dp.append(dp0)
for _ in range(n):
	dp1 = [0] * (n + 1)
	for i in range(n):
		dpi = dp0[i]
		s0 = set()
		for j in range(i + 1, n + 1):
			if not s[j] in s0:
				s0.add(s[j])
				dp1[j] += dpi
				dp1[j] = min(dp1[j], k)
	dp0 = list(dp1)
	dp.append(dp0)
ans = 0
for i in range(n, -1, -1):
	k0 = sum(dp[i])
	if k0 < k:
		ans += (n - i) * k0
		k -= k0
	else:
		ans += (n - i) * k
		k = 0
		break
if k > 0:
	ans = -1
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	(n, k) = RL()
	s = input()
	q = deque()
	q.append(s)
	res = 0
	rec = set()
	rec.add(s)
	while q:
		now = q.popleft()
		res += n - len(now)
		if len(rec) >= k:
			continue
		for i in range(len(now)):
			nex = now[:i] + now[i + 1:]
			if nex in rec:
				continue
			rec.add(nex)
			if len(rec) <= k:
				q.append(nex)
	print(res if len(rec) >= k else -1)
main()


(n, K) = map(int, input().split())
s = input()
J = [-1] * n
last_seen = dict()
for i in range(n):
	if s[i] in last_seen:
		J[i] = last_seen[s[i]]
	last_seen[s[i]] = i
dp = [[[0] * (1 + n) for _ in range(n)] for _ in range(n)]
for i in range(n):
	for j in range(i, n):
		dp[i][j][0] = 1
for k in range(1, 1 + n):
	for i in range(n):
		for j in range(i, n):
			if j - i + 1 < k:
				continue
			A = dp[i][j - 1][k]
			B = dp[i][j - 1][k - 1]
			if J[j] == -1:
				C = 0
			elif J[j] - 1 >= i:
				C = dp[i][J[j] - 1][k - 1]
			elif J[j] - 1 == i - 1 and k == 1:
				C = 1
			else:
				C = 0
			dp[i][j][k] = A + B - C
k = K
ans = 0
for size in range(n, -1, -1):
	if dp[0][n - 1][size] <= k:
		k -= dp[0][n - 1][size]
		ans += dp[0][n - 1][size] * (n - size)
	else:
		ans += k * (n - size)
		k = 0
		break
if k == 0:
	print(ans)
else:
	print(-1)


def check_word(word_list, word_need):
	unique = []
	for i in range(len(word_list)):
		if word_need == 0:
			break
		for j in range(len(word_list[i])):
			if word_need == 0:
				break
			new_word = word_list[i][:j] + word_list[i][j + 1:]
			if new_word not in unique:
				unique.append(new_word)
				word_need -= 1
	return unique

def check_all():
	cost_sum = 0
	cost_each = 1
	[raw_length, raw_size] = input().split()
	size = int(raw_size)
	words = input().split()
	size -= 1
	while size > 0:
		if len(words[0]) == 0:
			return -1
		words = check_word(words, size)
		cost_sum += len(words) * cost_each
		cost_each += 1
		size -= len(words)
	return cost_sum
print(check_all())


R = lambda : map(int, input().split())
(n, k) = R()
s = input()
p = [s]
ans = 0
d = set()
while p:
	q = p.pop(0)
	if q not in d:
		k -= 1
		ans += n - len(q)
		if k == 0:
			print(ans)
			quit()
		d.add(q)
		for i in range(len(q)):
			t = q[:i] + q[i + 1:]
			if t not in p:
				p.append(t)
print(-1)


(n, d) = 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
	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
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, k) = map(int, input().split())
s = input()
ns = len(s)
pos = [0 for i in range(26)]
dp = [[0 for j in range(ns + 1)] for i in range(ns + 1)]
dp[0][0] = 1
for i in range(1, ns + 1):
	v = ord(s[i - 1]) - ord('a')
	for j in range(0, i + 1):
		if j > 0:
			dp[i][j] += dp[i - 1][j - 1]
		dp[i][j] += dp[i - 1][j]
		if pos[v] >= 1 and j >= i - pos[v]:
			dp[i][j] -= dp[pos[v] - 1][j - (i - pos[v])]
	pos[v] = i
res = 0
for j in range(0, ns + 1):
	if k >= dp[ns][j]:
		res += dp[ns][j] * j
		k -= dp[ns][j]
	else:
		res += k * j
		k = 0
		break
print(res if k == 0 else -1)


import queue

def process_test_case():
	(n, k) = list(map(int, input().split()))
	S = input()
	if k == 1:
		return 0
	q = queue.Queue()
	output = set()
	cost = 0
	output.add(S)
	q.put((S, 0))
	while not q.empty():
		(string, point_cost) = q.get()
		for i in range(len(string)):
			temp = string[:i] + string[i + 1:]
			if temp not in output:
				output.add(temp)
				q.put((temp, point_cost + 1))
				cost += point_cost + 1
				if len(output) >= k:
					return cost
	if len(output) < k:
		return -1
	return cost
print(process_test_case())


(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
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
	cost += minct * localcost
if setsize == 0:
	print(cost)
else:
	print(-1)


(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


def main():
	(n, K) = map(int, input().split())
	s = str(input())
	next = [[10 ** 18] * 26 for _ in range(n + 1)]
	for i in reversed(range(n)):
		for j in range(26):
			next[i][j] = next[i + 1][j]
			if s[i] == chr(j + ord('a')):
				next[i][j] = i
	dp = [[0] * (n + 1) for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		for j in range(n + 1):
			for k in range(26):
				if next[i][k] >= n:
					continue
				elif j + 1 <= n:
					dp[next[i][k] + 1][j + 1] += dp[i][j]
	d = {}
	V = [0] * (n + 1)
	for i in range(n + 1):
		for j in range(n + 1):
			V[j] += dp[i][j]
	V.reverse()
	ans = 0
	for (i, v) in enumerate(V):
		if v >= K:
			ans += K * i
			break
		else:
			ans += v * i
			K -= v
	else:
		print(-1)
		exit()
	print(ans)
main()


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)


import queue

def solve(s, n, k):
	q = queue.Queue()
	q.put(s)
	st = set()
	st.add(s)
	while not q.empty() and len(st) < k:
		u = q.get()
		for i in range(len(u)):
			temp = u[0:i:1] + u[i + 1:len(u):1]
			if temp not in st:
				st.add(temp)
				q.put(temp)
				if len(st) == k:
					break
	if len(st) == k:
		ans = k * n
		for i in st:
			ans -= len(i)
		return ans
	return -1

def main():
	(n, k) = map(int, input().split())
	print(solve(input(), n, k))
main()


(n, k) = tuple([int(x) for x in input().split()])
s = input()
q = []
nv = ''
st = []
st.append(s)
ans = 0
q.append(s)
while q != [] and len(st) < k:
	v = q.pop(0)
	for i in range(len(v)):
		nv = v
		nv = nv[:i] + nv[i + 1:]
		if nv not in st and len(st) + 1 <= k:
			q.append(nv)
			st.append(nv)
			ans += n - len(nv)
if len(st) < k:
	print(-1)
else:
	print(ans)


def f(s, k):
	n = len(s)
	q = [s]
	S = set()
	S.add(s)
	ans = 0
	while len(q) > 0 and k > 0:
		ss = q[0]
		k -= 1
		ans += n - len(ss)
		q.pop(0)
		for i in range(len(ss)):
			ns = ss[0:i] + ss[i + 1:len(s)]
			if ns not in S:
				q.append(ns)
				S.add(ns)
	if k == 0:
		return ans
	return -1

def main():
	(n, k) = map(int, input().split())
	s = input()
	print(f(s, k))
main()


class const:
	size = 26
(n, k) = 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
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]
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)
	exit()
print(ans)


from collections import deque
(n, k) = map(int, input().split())
s = input()
dq = deque([s])
ans = 0
visited = set()
while k and dq:
	cs = dq.popleft()
	k -= 1
	ans += len(s) - len(cs)
	for i in range(len(cs)):
		if cs[:i] + cs[i + 1:] in visited:
			continue
		visited.add(cs[:i] + cs[i + 1:])
		dq.append(cs[:i] + cs[i + 1:])
print(-1 if k else ans)


from collections import deque
(n, k) = map(int, input().split())
st = input()
queue = deque()
set1 = set()
set1.add(st)
queue.append(st)
count = 1
ans = 0
while queue and count < k:
	p = queue.popleft()
	for i in range(len(p)):
		word = p[:i] + p[i + 1:]
		if word not in set1:
			set1.add(word)
			queue.append(word)
			if count < k:
				ans += n - len(word)
			count += 1
if count < k:
	print(-1)
else:
	print(ans)


a = input()
n = int(a.split(' ')[0])
k = int(a.split(' ')[1])
s = input()
lgmoorz = []
dpprev = []
dpcurr = []
dp = []
for i in range(len(s)):
	if s[i] not in lgmoorz:
		lgmoorz.append(s[i])
	dpcurr.append(len(lgmoorz))
dp.append(dpcurr[-1])
prevocc = []
for i in range(len(s)):
	prevocc.append(-1)
	for j in range(i - 1, -1, -1):
		if s[j] == s[i]:
			prevocc[-1] = j
			break
for i in range(2, n + 1):
	dpprev = dpcurr
	dpcurr = []
	for j in range(i - 1):
		dpcurr.append(0)
	for j in range(i - 1, n):
		dpcurr.append(dpcurr[-1])
		dpcurr[-1] += dpprev[j - 1]
		if prevocc[j] >= i - 1:
			dpcurr[-1] -= dpprev[prevocc[j] - 1]
	dp.append(dpcurr[-1])
dp = [1] + dp
curr = 0
for i in range(n, -1, -1):
	tadd = min(dp[i], k)
	cost = n - i
	curr += tadd * cost
	k -= tadd
	if k == 0:
		break
if k == 0:
	print(curr)
else:
	print(-1)


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 sys
(n, k) = [int(i) for i in input().split()]
s = input()
seqset = set()
seqset.add(s)
subsequences = [[] for _ in range(n)]
subsequences[0].append(s)
result = 0
count = 1
if count == k:
	print(result)
	sys.exit(0)
for i in range(n - 1):
	for ss in subsequences[i]:
		for j in range(len(ss)):
			temp = ss[:j] + ss[j + 1:]
			if temp not in seqset:
				subsequences[i + 1].append(temp)
				seqset.add(temp)
				result += n - len(temp)
				count += 1
			if count == k:
				print(result)
				sys.exit(0)
if k - count == 1:
	print(result + n)
else:
	print(-1)