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

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

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

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

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


-----Input-----

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

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


-----Output-----

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


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

Output
4

Input
5 6
aaaaa

Output
15

Input
5 7
aaaaa

Output
-1

Input
10 100
ajihiushda

Output
233



-----Note-----

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

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Dynamic programming


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


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


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)


(n, k) = list(map(int, input().split()))
s = '$' + input()
cnt = [[0] * (n + 1) for i in range(n + 1)]
cnt[0][0] = 1
for l in range(1, n + 1):
	for i in range(l, n + 1):
		used = [False] * 26
		for j in range(i, n + 1):
			x = ord(s[j]) - ord('a')
			if not used[x]:
				cnt[l][j] += cnt[l - 1][i - 1]
				used[x] = True
ans = 0
for l in range(n, -1, -1):
	s = sum(cnt[l])
	if s < k:
		ans += (n - l) * s
		k -= s
	else:
		ans += (n - l) * k
		k = 0
		break
if k > 0:
	ans = -1
print(ans)


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


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


def naiveSolve():
	return

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

def main():
	(n, k) = readIntArr()
	s = input()
	arr = [charToInt(c) for c in s]
	dp = [[0 for _ in range(n + 1)] for __ in range(n)]
	for i in range(n):
		dp[i][1] = 1
	prevLatestIdx = [-1] * 26
	for i in range(n):
		for l in range(2, n + 1):
			for c in range(26):
				if prevLatestIdx[c] != -1:
					dp[i][l] += dp[prevLatestIdx[c]][l - 1]
		prevLatestIdx[arr[i]] = i
	cnts = [0] * (n + 1)
	for c in range(26):
		if prevLatestIdx[c] != -1:
			for l in range(1, n + 1):
				cnts[l] += dp[prevLatestIdx[c]][l]
	cnts[0] = 1
	cost = 0
	for l in range(n, -1, -1):
		diff = min(k, cnts[l])
		cost += diff * (n - l)
		k -= diff
	if k == 0:
		print(cost)
	else:
		print(-1)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys

class HSubsequencesHardVersion:

	def solve(self):
		(n, k) = [int(_) for _ in input().split()]
		s = input()
		dp = [[0] * (n + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		last = {key: -1 for key in (chr(x) for x in range(ord('a'), ord('z') + 1))}
		for i in range(1, n + 1):
			dp[i][0] = 1
			for j in range(1, i + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - (dp[last[s[i - 1]]][j - 1] if last[s[i - 1]] != -1 else 0)
			last[s[i - 1]] = i - 1
		ans = 0
		tot = 0
		for sz in range(n, -1, -1):
			ans += min(k - tot, dp[n][sz]) * (n - sz)
			tot = min(k, tot + dp[n][sz])
			if tot == k:
				break
		if tot >= k:
			print(ans)
		else:
			print(-1)
solver = HSubsequencesHardVersion()
input = sys.stdin.readline
solver.solve()


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


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


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


import sys
input = sys.stdin.readline
xx = 'abcdefghijklmnopqrstuvwxyz'
yy = {}
for i in range(26):
	yy[xx[i]] = i
(n, kk) = map(int, input().split())
st = list(input())[:-1]
count_ar = [0] * n
se = [-1] * 26
count = 0
for i in range(n - 1, -1, -1):
	se[yy[st[i]]] = i
	count_ar[i] = se.copy()
count_ar.append([])
main = [1]
freq_ind = [0] * n
nex = [0] * n
se = set({})
for i in range(n):
	if not st[i] in se:
		freq_ind[i] = 1
		se.add(st[i])
for i in range(2, n + 2):
	for j in range(n):
		for k in count_ar[j + 1]:
			if k != -1:
				nex[k] += freq_ind[j]
	main.append(sum(freq_ind))
	freq_ind = nex.copy()
	nex = [0] * n
ans = 0
for i in range(n, -1, -1):
	if kk <= main[i]:
		ans += kk * (n - i)
		kk = 0
		break
	else:
		ans += main[i] * (n - i)
		kk -= main[i]
if kk == 0:
	print(ans)
else:
	print(-1)


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)


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


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


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]
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)
		return
else:
	print(-1)


class const:
	size = 26
(n, k) = list(map(int, input().split()))
s = input()
maxpos = [[-1 for _ in range(const.size)] for _ in range(n)]
for i in range(n):
	for j in range(const.size):
		if i > 0:
			maxpos[i][j] = maxpos[i - 1][j]
	maxpos[i][ord(s[i]) - ord('a')] = i
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)
	return
print(ans)


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


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


line1 = input().split(' ')
n = int(line1[0])
k = int(line1[1])
s = list(input())
dp = [101 * [0] for i in range(101)]
last = 26 * [-1]
for i in range(n + 1):
	dp[0][i] = 1
for l in range(1, n + 1):
	dp[l][0] = 0
	for c in range(26):
		last[c] = -1
	for i in range(1, n + 1):
		dp[l][i] = dp[l - 1][i - 1] + dp[l][i - 1]
		if last[ord(s[i - 1]) - ord('a')] != -1:
			dp[l][i] -= dp[l - 1][last[ord(s[i - 1]) - ord('a')] - 1]
		last[ord(s[i - 1]) - ord('a')] = i
i = 0
res = 0
while i <= n and k >= 0:
	c = min(k, dp[n - i][n])
	k -= c
	res += c * i
	i += 1
if k > 0:
	print(-1)
else:
	print(res)


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


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


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


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


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)


def subsequences_of_length(s):
	n = len(s)
	alphabet = 'abcdefghijklmnopqrstuvwxyz'
	to_int = {}
	for (i, char) in enumerate(alphabet):
		to_int[char] = i
	next_i = [[n] * len(alphabet) for i in range(n + 1)]
	for i in reversed(range(n)):
		for (j, char) in enumerate(alphabet):
			next_i[i][j] = next_i[i + 1][j]
		next_i[i][to_int[s[i]]] = i
	dp = [[0] * (n + 1) for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(n):
		for k in range(n):
			for j in range(26):
				if next_i[i][j] >= n:
					continue
				dp[k + 1][next_i[i][j] + 1] += dp[k][i]
	ans = [sum(dp[i]) for i in range(n + 1)]
	return ans
(n, k) = map(int, input().split())
s = input()
ans_len = subsequences_of_length(s)
ans_cnt = 0
ans = 0
for length in reversed(range(len(ans_len))):
	cnt = ans_len[length]
	if ans_cnt + cnt <= k:
		ans_cnt += cnt
		ans += cnt * (n - length)
	else:
		ans += (k - ans_cnt) * (n - length)
		ans_cnt = k
if ans_cnt != k:
	print(-1)
else:
	print(ans)


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)


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)


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, d) = list(map(int, input().split()))
s = input()
t = [[-1 for i in range(n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i, n + 1):
		if j == i:
			t[i][j] = 1
		else:
			t[i][j] = 0
jes = [0] * 300
for i in range(1, n + 1):
	jes[ord(s[i - 1])] = 1
	t[i][1] = sum(jes)
for j in range(2, n + 1):
	ind = [-1] * 300
	ind[ord(s[j - 1])] = j - 1
	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)


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


(n, K) = list(map(int, input().split()))
s = input()
max_n = 104
dp = [[0] * max_n for i in range(max_n)]
s = '$' + s
for i in range(n + 1):
	dp[0][i] = 1
for ln in range(1, n + 1):
	for j in range(1, n + 1):
		dp[ln][j] = dp[ln][j - 1] + dp[ln - 1][j - 1]
		for k in range(j - 1, 0, -1):
			if s[k] == s[j]:
				dp[ln][j] -= dp[ln - 1][k - 1]
				break
ans = 0
for ln in range(n, -1, -1):
	cnt = dp[ln][n]
	if cnt < K:
		ans += cnt * (n - ln)
		K -= cnt
	else:
		ans += K * (n - ln)
		K = 0
		break
if K != 0:
	print(-1)
else:
	print(ans)


from string import ascii_lowercase
(n, k) = map(int, input().split())
s = input()
todo = [1] + [0] * n
dp = {letter: [0] * (n + 1) for letter in ascii_lowercase}
for letter in s:
	prev = dp[letter]
	dp[letter] = [0] + todo[:n]
	todo = [a - b + c for (a, b, c) in zip(todo, prev, dp[letter])]
answer = 0
for (cost, amt) in enumerate(todo[::-1]):
	if k > amt:
		k -= amt
		answer += amt * cost
	else:
		answer += k * cost
		k = 0
		break
print(-1 if k else answer)


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