Appleman has n cards. Each card has an uppercase letter written on it. Toastman must choose k cards from Appleman's cards. Then Appleman should give Toastman some coins depending on the chosen cards. Formally, for each Toastman's card i you should calculate how much Toastman's cards have the letter equal to letter on ith, then sum up all these quantities, such a number of coins Appleman should give to Toastman.

Given the description of Appleman's cards. What is the maximum number of coins Toastman can get?


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10^5). The next line contains n uppercase letters without spaces — the i-th letter describes the i-th card of the Appleman.


-----Output-----

Print a single integer – the answer to the problem.


-----Examples-----
Input
15 10
DZFDFZDFDDDDDDF

Output
82

Input
6 4
YJSNPI

Output
4



-----Note-----

In the first test example Toastman can choose nine cards with letter D and one additional card with any letter. For each card with D he will get 9 coins and for the additional card he will get 1 coin.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
arr = [0] * 26
s = input()
aux = ord('A')
for i in range(len(s)):
    arr[ord(s[i]) - aux] += 1
arr.sort(reverse = True)
i = 0
sum = 0
while k > 0:
    if arr[i] >= k:
        sum += k ** 2
        k = 0
    else:
        k -= arr[i]
        sum += arr[i] ** 2
        i += 1
print(sum)

import sys

n, k = [int(x) for x in sys.stdin.readline().split()]
cards = sys.stdin.readline().strip()
count = [0]*26
for letter in cards:
    count[ord(letter) - ord('A')] += 1
count.sort()
count.reverse()
coins = 0
i = 0
while k > 0 and i < 26:
    if count[i] <= k:
        coins += count[i]*count[i]
        k -= count[i]
    else:
        coins += k*k
        k = 0
    i += 1
print(coins)

a, b = list(map(int, input().split()))
n = {chr(i): 0 for i in range(ord('A'), ord('Z') + 1)}
for c in input():
    n[c] += 1

ans = 0
for i in sorted(list(n.values()), reverse=True):
    x = min(i, b)
    ans += x * x
    b -= x
    if not b:
        break

print(ans)


n,k=list(map(int,input().split()))
m=input()
d={chr(ord('A')+i):0 for i in range(26)}
for ch in m:
    d[ch]+=1;
nw=[[ch,d[ch]] for ch in d]
fl=True;
while fl:
    fl=False
    for i in range(25):
        if(nw[i][1]<nw[i+1][1]):
            d=nw[i][:]
            nw[i]=nw[i+1][:]
            nw[i+1]=d[:]
            fl=True
s=0
i=0
while k>0:
    if k>=nw[i][1]:
        s+=nw[i][1]**2
        k-=nw[i][1]
    else:
        s+=k**2
        k=0
    i+=1
print(s)


n,k = list(map(int,input().split()))
new_dict = {}
t = input()
for x in t:
	if x in new_dict:
		new_dict[x]=new_dict[x]+1
	else:
		new_dict[x]=1

p=0

#print(new_dict.items())

while(k>0):
	if(new_dict[max(new_dict, key=new_dict.get)]>=k):
		p = p + k**2;
		k = 0
	else:
		p = p + new_dict[max(new_dict, key=new_dict.get)]**2
		k = k - new_dict[max(new_dict, key=new_dict.get)]
		del new_dict[max(new_dict, key=new_dict.get)]
	#	print("hello\n")
print(p)


n, k = list(map(int, input().split()))
s = input()
a = [0] * 26
for i in s:
    a[ord(i) - ord("A")] += 1
a.sort()
a = a[::-1]
i = 0
b = []
k1 = k
while i < n and k1 > 0:
    b.append(min(k1, a[i]))
    k1 -= a[i]
    i += 1
ans = 0
for i in b:
    ans += i * i
print(ans)


import operator

table = {}

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

chain = input()

for ch in chain:
  if ch in table:
    table[ch] += 1
  else:
    table[ch] = 1

sorted_table = ((k, table[k]) for k in sorted(table, key=table.get, reverse=True))

total = 0
for key, value in sorted_table:
  total += min(k, value) * min(k, value)
  k -= value
  if k <= 0:
    break
print(total)

import collections


n, k = list(map(int, str.split(input())))
coins = 0
for _, count in collections.Counter(input()).most_common():

    count = min(count, k)
    coins += count ** 2
    k -= count
    if k == 0:

        break

print(coins)


(n, k) = list(map(int, input().split()))
s = input()
d = [0] * 26
for i in range(n):
    d[ord(s[i]) - 65] += 1
d.sort()
ans = 0
while k > 0:
    if k < d[-1]:
        ans += k * k
        break
    else:
        k -= d[-1]
        ans += d[-1] * d[-1]
        d.pop()
print(ans)
    


temp = input().split()
N, K = int(temp[0]), int(temp[1])
s = input()
d = dict()
for c in s:
    d[c] = d.get(c, 0) + 1

sum = 0
while (K > 0):
    m = '-'
    for k, v in list(d.items()):
        if d.get(m, 0) < v:
            m = k

    if K > d[m]:
        sum += d[m] * d[m]
        K -= d[m]
    else:
        sum += K * K
        K = 0
    d[m] = 0
print (sum)



n,k = list(map(int, input().split()))
s = input()
ch = []
re = {}
limit = len(s)
c = 1
for i in range(limit):
    #print(s[i])
    if s[i] in re :
        re[s[i]] += 1
    else:
        re[s[i]] = 1
        ch.append(s[i])
li = len(ch)
score = []
for i in range(li):
    score.append(re[ch[i]])
score.sort(reverse = True)
#print(score)
last = len(score)
out = 0
for i in range(last):
    if k == 0 :
        break
    if k == score[i]:
        out  += score[i] * score[i]
        break
    elif k > score[i] :
        out += score[i] * score[i]
        k -= score[i]
    elif k < score[i]:
        out += k * k
        break
   # print(out)
print(out)
    


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

vv=list()
vc=list()

for i in s:
    if i not in vv:
        vv.append(i)
        vc.append(s.count(i))
vc.sort()
sum=0
for i in range(len(vc)-1,-1,-1):
    if vc[i]<k:
        sum+=(vc[i]**2)
        k-=vc[i]
    else:
        sum+=(k**2)
        break
print(sum)
    
        



def main():
	n, k = [ int(i) for i in input().split(' ') ]
	cards = input()
	letters = []
	for i in range(n):
		if cards[i] not in letters:
			letters.append(cards[i])
	l = len(letters)
	freq = [ 0 for i in range(l) ]
	for i in range(l):
		freq[i] = cards.count(letters[i])
	total = 0
	while k != 0:
		m = max(freq)
		if m > k:
			total = total + (k * k)
			k = 0
		else:
			k = k - m
			total = total + (m * m)
			freq.remove(m)
	print(total)


main()

n,k=map(int,input().split())
s=list(input())
a=[0 for i in range(26)]
for i in s:
	a[ord(i)-ord('A')]+=1
a.sort()
a.reverse()
i=0
s=0
while k!=0:
	if a[i]<=k:
		s+=a[i]*a[i]
		k-=a[i]
	else:
		s+=k*k 
		k=0
	i+=1

print(s)

n,k=list(map(int,input().split()))
m=26
d=[0]*m
c=input()
for e in c:
    d[ord(e)-65]+=1
d.sort(reverse=True)
ans=0
res=0
for i in range(m):
    if ans>=k:
        break
    if ans+d[i]<=k:
        ans+=d[i]
        res+=d[i]*d[i]
    else:
        res+=(k-ans)*(k-ans)
        ans=k
print(res)


count = [0]*26
n, k = list(map(int , input().split()))
cards = input()
for c in cards:
	count[ord(c)-ord('A')]+=1

count.sort(reverse=True)
ans = 0
for c in count:
	if (k - c) >= 0:
		ans += c**2
		k-=c
	else:
		ans += k**2
		break

print(ans)


this=input()
hurry=this.split()
n=int(hurry[0])
k=int(hurry[1])
then=input()
thelist=[]
i=0
while i<len(then):
    thelist.append(then[i])
    i+=1
#print(thelist)

checked=[]
counts=[]
for item in thelist:
    if item not in checked:
        checked.append(item)
        counts.append(thelist.count(item))
#print(checked)
#print(counts)
thetotal=0
while k>0:
    x=max(counts)
    if x>=k:
        print(thetotal+k*k)
        k=0
    else:
        thetotal+= x*x
        k-=x
        q=counts.index(x)
        #print(q)
        counts.remove(x)
        checked.remove(checked[q])


n, k = list(map(int, input().split()))
s = input()
A = [0 for i in range(26)]
for i in s:
    A[ord(i) - 65] += 1
A.sort()
i = 25
##taked = 0
ans = 0
##tk = k 
##for j in range(k):
##    A[i] -= 1
##    taked += 1
##    if A[i] == 0:
##        i -= 1
##        ans += taked * taked
##        tk -= taked
##        taked = 0
##    else:
##        if j == k - 1 and tk == k:
##            ans += taked * taked
##if tk == 1 and k != 1:
##    ans += 1
while k > 0:
    k -= A[i]
    ans += A[i] * A[i]
    i -= 1
if k < 0:
    k += A[i + 1]
    ans -= A[i + 1] * A[i + 1]
    ans += k * k
    
print(ans)


a, b = list(map(int, input().split(' ')))
string = input()
chars = [x for x in string]
chars2 = set(chars)
chars2 = sorted(chars2, key = lambda x:chars.count(x))
chars2.reverse()

count = [chars.count(x) for x in chars2]
points = 0
cards = 0
for i in range(len(count)):
    if cards + count[i] >= b:
        break
    else:
        cards += count[i]
        points += count[i]**2
points += (b-cards)**2
print(points)


n,k=list(map(int,input().split()))
s=input()
a=[0]*26
for c in s:
    a[ord(c)-ord('A')]+=1
a.sort(reverse=True)
ans=0
for i in range(26):
    if(k<=a[i]):
        ans+=k**2
        break
    else:
        ans+=a[i]**2
        k-=a[i]
print(ans)


from collections import Counter


def __starting_point():
    n, k = [int(i) for i in input().split()]
    
    c = Counter(input())

    res = 0
    tmp = k

    for w, n in c.most_common():
        if tmp > n:
            tmp -= n
            res += n * n
        else:
            res += tmp * tmp
            break
    print(res)


__starting_point()

n, k = list(map(int, input().split()))
s = input()
count = {}
for c in s:
  count[c] = count.get(c, 0) + 1
a = sorted(list(count.values()), reverse=True)
coins = 0
for c in a:
  if c >= k:
    coins += k * k
    break
  coins += c * c
  k -= c
print(coins)


n,k = map(int,input().split())
s=input().lower()
ans=0
letters=[0 for i in range(ord('z')+1)]
for c in s:
    letters[ord(c)]+=1
while k>0:
    ans+=min(k,max(letters))**2
    k-=max(letters)
    letters[letters.index(max(letters))]=0
print(ans)

n,k=list(map(int,input().split()))
inpt=input()
Main=[0]*26
for count in inpt:
    Main[ord(count)-ord('A')]+=1
Main.sort(reverse=True)
MainPrint=0
for i in range(26):
    if k<=Main[i]:
        MainPrint+=k**2
        break
    else:
        MainPrint+=Main[i]**2
        k-=Main[i]
print(MainPrint)