Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

As a health expert, Vinay is keeping a close watch on the ongoing pandemic of coronavirus disease (COVID-19). He thought of a different situation where there are $26$ types of viruses, named "aorona", "borona", "corona", ..., "zorona".

You are given a string $S$ with length $N$. There are $N$ people (numbered $1$ through $N$) and for each valid $i$, the $i$-th person is infected by exactly one type of virus named $S_{i}$orona (i.e. "corona" with the first letter replaced by the $i$-th character of $S$).

You should answer $Q$ queries. In each query:
You are given an integer $C$ denoting the number of available *isolation centers*.
Each isolation center has an infinite capacity, but with the restriction that two people infected with the same type of virus cannot stay in the same isolation center.
There is also a *pending queue* with an infinite capacity and there are no restrictions on which people can be in the pending queue.
Initially, the isolation centers and pending queue are empty.
Each of the $N$ people should be placed in either the pending queue or one of the isolation centers.
Since Vinay is busy finding a vaccine, he asks Swapnil to find a way to place the people in the pending queue and isolation centers such that the number of people in the pending queue is the smallest possible.
Help Swapnil find the size of the pending queue in that case.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains a single string $S$.
Each of the following $Q$ lines contains a single integer $C$ describing a query.

------  Output ------
For each query, print a single line containing one integer ― the minimum size of the pending queue.

------  Constraints ------
$1 ≤ T, N, Q ≤ 10^{5}$
$0 ≤ C ≤ 10^{9}$
$|S| = N$
$S$ contains only lowercase English letters
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $Q$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (20 points): $T, N, Q, C ≤ 10$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
1

20 2

stayinghomesaveslife

1

3
----- Sample Output 1 ------ 
6

0
----- explanation 1 ------ 
Example case 1: In the pending queue for the first query, there should be $2$ people with "eorona", $2$ with "sorona", $1$ with "aorona" and $1$ with "iorona".

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


Solutions:
from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	dic = Counter(s)
	for i in range(q):
		p = 0
		ic = int(input())
		for j in dic:
			if dic[j] > ic:
				p += dic[j] - ic
		print(p)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = list(input())
	s1 = [s.count(i) for i in set(s)]
	for i in range(q):
		v = 0
		c = int(input())
		for i in s1:
			if i > c:
				v += i - c
		print(v)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	ds = dict(Counter(s))
	for __ in range(q):
		c = int(input())
		ans = 0
		for (x, y) in ds.items():
			ans += max([0, y - c])
		print(ans)


import collections
for _ in range(int(input())):
	(n, q) = [int(k) for k in input().split()]
	s = input()
	d = collections.Counter(s)
	values = list(d.values())
	for j in range(q):
		cnt = 0
		c = int(input())
		for l in values:
			if l > c:
				cnt += l - c
		print(cnt)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	dic = {}
	for i in range(len(s)):
		dic[s[i]] = dic.get(s[i], 0) + 1
	for i in range(q):
		c = int(input())
		count = 0
		for i in dic:
			if dic[i] > c:
				count += dic[i] - c
		print(count)


for i in range(int(input())):
	from collections import Counter
	(n, c) = map(int, input().split())
	s = input()
	t = list(Counter(s).values())
	for i in range(c):
		total = 0
		x_i = int(input())
		if x_i >= max(t):
			print(0)
		else:
			for j in range(len(t)):
				if x_i < t[j]:
					total += t[j] - x_i
			print(total)


x = int(input())
final = []
for ij in range(0, x):
	yui = str(input())
	yre = yui.split(' ')
	jew = []
	for ix in yre:
		jew.append(int(ix))
	b = str(input())
	cfr = [b]
	for llp in range(0, jew[-1]):
		gxz = int(input())
		cfr.append(gxz)
	final.append(cfr)
for bbv in final:
	w = bbv[0]
	bbv.pop(0)
	kl = {}
	for mmu in w:
		if mmu in list(kl.keys()):
			kl[mmu] += 1
		else:
			kl[mmu] = 1
	for yyy in bbv:
		pend = 0
		for hte in list(kl.keys()):
			ip = kl[hte]
			if ip > yyy:
				pend += ip - yyy
		print(pend)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = list(input())
	freq = [0] * 26
	for ele in s:
		freq[ord(ele) - 97] += 1
	for i in range(q):
		m = int(input())
		count = 0
		for j in range(26):
			if freq[j] > m:
				count += freq[j] - m
		print(count)


M = int(input())
while M > 0:
	(n, q) = map(int, input().split(' '))
	s = input()
	freq = {}
	for i in s:
		if i in freq:
			freq[i] += 1
		else:
			freq[i] = 1
	li = list(freq.values())
	max1 = max(li)
	for i in range(q):
		count = 0
		c = int(input())
		for j in li:
			if j > c:
				l = j - c
				count += l
		print(count)
	M = M - 1


from collections import Counter
for tc in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	a = Counter(s)
	c = 0
	for i in range(q):
		pend = 0
		c = int(input())
		for j in a.values():
			if j > c:
				pend += j - c
		print(pend)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for __ in range(q):
		total = 0
		c = int(input())
		for (i, j) in d.items():
			if j > c:
				total += j - c
		print(total)


from collections import Counter
for t in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	c = Counter(s)
	for i in range(q):
		d = int(input())
		co = 0
		for val in c.values():
			if val > d:
				co += val - d
		print(co)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	d1 = {ele: s.count(ele) for ele in s}
	l1 = list(d1.values())
	for i in range(q):
		ans = 0
		c = int(input())
		for z in l1:
			if z > c:
				ans += z - c
		print(ans)


from collections import Counter
t = int(input())
for i in range(t):
	(n, q) = list(map(int, input().split(' ')))
	string = input()
	letter_dict = dict(Counter(string))
	for j in range(q):
		c = int(input())
		result = 0
		for key in list(letter_dict.values()):
			if key > c:
				result += key - c
		print(result)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = str(input())
	d = {}
	for i in range(n):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	for i in range(q):
		c = int(input())
		s = 0
		for j in list(d.keys()):
			if d[j] - c > 0:
				s += d[j] - c
		print(s)


testcases = int(input())
for i in range(testcases):
	(n, q) = map(int, input().split())
	s = str(input())
	freq = {}
	data = []
	count = 0
	for i in s:
		if i not in freq:
			freq[i] = 1
		else:
			freq[i] += 1
	for i in range(q):
		val = int(input())
		if val == 1:
			temp = []
			for key in freq:
				if freq[key] > 1:
					temp.append(freq[key] - 1)
			if len(temp) == 0:
				print(0)
			else:
				print(sum(temp))
		else:
			temp = []
			for key in freq:
				if freq[key] > val:
					diff = freq[key] - val
					temp.append(diff)
			print(sum(temp))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	count = [0] * 26
	for ch in s:
		count[ord(ch) - 97] += 1
	for i in range(q):
		c = int(input())
		queued = 0
		for val in count:
			if val > c:
				queued += val - c
		print(queued)


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	s = input()
	lis = []
	for i in range(q):
		c = int(input())
		lis.append(c)
	myd = {}
	for i in range(len(s)):
		myd.update({s[i]: s.count(s[i])})
	v = list(myd.values())
	sm = 0
	lis1 = []
	for i in range(len(lis)):
		for j in range(len(v)):
			if v[j] > lis[i]:
				x = v[j] - lis[i]
				sm += x
		lis1.append(str(sm))
		sm = 0
	print('\n'.join(lis1))


from collections import Counter
for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	c = [int(input()) for i in range(q)]
	s = Counter(s)
	for i in c:
		if i >= max(s.values()):
			print(0)
		else:
			res = 0
			for k in s.keys():
				res += max(s.get(k, 0) - i, 0)
			print(res)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	t = Counter(s).values()
	for i in range(q):
		count = 0
		c = int(input())
		for j in t:
			if j > c:
				count += j - c
		print(count)


from collections import Counter
testcase = int(input())
for i in range(testcase):
	(n, q) = map(int, input().split())
	temp_str = str(input())
	patient_str = [x for x in temp_str]
	lst = Counter(patient_str)
	for cq in range(0, q):
		cq = int(input())
		res = 0
		for a in lst:
			if lst[a] > cq:
				res += lst[a] - cq
		print(res)


for _ in range(int(input())):
	from collections import Counter
	(n, q) = map(int, input().split())
	s = input()
	c = Counter(s).values()
	for i in range(q):
		k = 0
		w = int(input())
		for i in c:
			if i > w:
				k += i - w
		print(k)


from collections import Counter
for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	x = Counter(s)
	y = x.values()
	for j in range(q):
		s = 0
		c = int(input())
		for i in y:
			if i > c:
				s += i - c
		print(s)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = input()
	d = dict()
	for i in set(s):
		d[i] = s.count(i)
	for i in range(q):
		c = int(input())
		r = 0
		for j in d.values():
			if j - c > 0:
				r = r + (j - c)
		print(r)


from collections import Counter
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
mod = lambda n: n % (10 ** 9 + 7)
sl = lambda l: list(set(l))
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : input()
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	(numOfPeople, numOfQueries) = sepi()
	virusTypes = soi()
	virusCount = Counter(virusTypes).values()
	for i in range(numOfQueries):
		pendingQueue = 0
		isolationCenters = ii()
		for i in virusCount:
			pendingQueue += max(0, i - isolationCenters)
		print(pendingQueue)


from collections import Counter
T = int(input())
for _ in range(T):
	(N, Q) = list(map(int, input().split()))
	S = input()
	virus_count = Counter(S).values()
	for _ in range(Q):
		isolation_center = int(input())
		pending_count = 0
		for count in virus_count:
			if count > isolation_center:
				pending_count += count - isolation_center
		print(pending_count)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	freq = Counter(s)
	key = list(freq.keys())
	value = list(freq.values())
	len_value = len(value)
	max_value = max(value)
	for i in range(q):
		c = int(input())
		if c >= max_value:
			print(0)
		elif c == 0:
			print(sum(value))
		else:
			cp = 0
			for it in value:
				if it > c:
					cp += it - c
			print(cp)


import collections
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	virus = input()
	v = collections.Counter(virus)
	mem = v.values()
	for j in range(q):
		iso = int(input())
		pend_q = 0
		for i in mem:
			if i > iso:
				pend_q += i - iso
		print(pend_q)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	st = input()
	st_set = set(st)
	li = [st.count(i) for i in st_set]
	for _ in range(q):
		size = int(input())
		cli = [j - size for j in li if j > size]
		print(sum(cli))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	l = [0] * 27
	for i in s:
		l[ord(i) - 96] = l[ord(i) - 96] + 1
	for j in range(q):
		v = int(input())
		cnt = 0
		for k in l:
			if k > v:
				cnt = cnt + abs(k - v)
		print(cnt)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	a = [0] * 26
	for i in s:
		a[ord(i) - 97] += 1
	for _ in range(q):
		m = int(input())
		sums = sum(a)
		for i in range(26):
			if a[i] >= m:
				sums -= m
			else:
				sums -= a[i]
		print(sums)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	a = Counter(s)
	ob = a.values()
	for _ in range(q):
		c = int(input())
		pending = 0
		for i in ob:
			if i > c:
				pending += i - c
		print(pending)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	sit = input()
	list1 = [0 for x in range(26)]
	for y in sit:
		list1[ord(y) - 97] += 1
	for j in range(q):
		count1 = 0
		c = int(input())
		for z in list1:
			if z > c:
				count1 += z - c
		print(count1)


T = int(input())
for i in range(T):
	(N, Q) = map(int, input().split())
	S = input()
	S.lower()
	A = []
	for j in S:
		A.append(j)
	A = list(set(A))
	c = []
	for k in range(len(A)):
		m = 0
		for j in S:
			if j == A[k]:
				m = m + 1
		c.append(m)
	for i in range(Q):
		l = 0
		C = int(input())
		for i in range(len(c)):
			if c[i] > C:
				l = l + c[i] - C
		print(l)


import string
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = input()
	l = list(string.ascii_lowercase)
	c = []
	for i in range(26):
		c.append(0)
	for i in range(len(s)):
		for j in range(26):
			if s[i] == l[j]:
				c[j] = c[j] + 1
	for j in range(q):
		sum = 0
		p = int(input())
		for i in range(26):
			if c[i] > p:
				sum = sum + (c[i] - p)
		print(sum)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	j = set(s)
	l = []
	for i in j:
		l.append(s.count(i))
	for _ in range(q):
		c = int(input())
		k = 0
		for i in l:
			if i - c > 0:
				k += i - c
		print(k)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	arr = []
	l = []
	for e in s:
		if e not in arr:
			arr.append(e)
	for j in arr:
		l.append(s.count(j))
	for i in range(q):
		count = 0
		c = int(input())
		for item in l:
			if item > c:
				count += item - c
		print(count)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(input())
	l1 = []
	for _ in range(y):
		l1.append(int(input()))
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	l2 = [v for (k, v) in d.items()]
	for i in l1:
		s = 0
		for j in l2:
			if j > i:
				s = s + j - i
		print(s)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	string = input()
	freq = dict(Counter(string))
	while q:
		centers = int(input())
		ans = 0
		for cnt in freq.values():
			ans += max(cnt - centers, 0)
		print(ans)
		q -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	l = []
	for _ in range(q):
		l.append(int(input()))
	dt = {}
	count = 0
	for i in range(n):
		if s[i] in dt:
			dt[s[i]] = dt.get(s[i]) + 1
			count += 1
		else:
			dt[s[i]] = 1
	for qi in l:
		sum = 0
		for value in dt.values():
			if value - qi > 0:
				sum += value - qi
		print(sum)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	f = {}
	for i in s:
		if i in f:
			f[i] += 1
		else:
			f[i] = 1
	for i in range(q):
		a = int(input())
		count = 0
		for i in f:
			if f[i] > a:
				count += f[i] - a
		print(count)


n = int(input())
for i in range(n):
	(x, y) = (int(i) for i in input().split())
	s = input()
	a = set(s)
	l = []
	j = []
	for i in a:
		l.append(s.count(i))
	for i in range(y):
		c = 0
		k = int(input())
		for i in range(len(a)):
			h = l[i] - k
			if h > 0:
				c += h
		print(c)


for _ in range(int(input())):
	(n, q) = [int(x) for x in input().split(' ')]
	s1 = input()
	arr = [0] * 26
	for i in range(26):
		arr[i] = s1.count(chr(i + 97))
	for __ in range(q):
		sum1 = 0
		c = int(input())
		for i in range(26):
			if arr[i] - c > 0:
				sum1 += arr[i] - c
		print(sum1)


tests = int(input())
for i in range(tests):
	(n, q) = map(int, input().split())
	string = input()
	unique_char = {}
	for x in string:
		if x in unique_char:
			unique_char[x] += 1
		else:
			unique_char[x] = 1
	for x in range(q):
		ans = 0
		centers = int(input())
		for y in unique_char.keys():
			addition = unique_char[y] - centers
			if addition > 0:
				ans += addition
		print(ans)


for _ in range(int(input().strip())):
	(n, q) = list(map(int, input().strip().split()))
	s = input().strip()
	hash = {}
	for c in s:
		hash[c] = hash.get(c, 0) + 1
	R = []
	for _ in range(q):
		t = int(input().strip())
		ans = 0
		for k in hash.keys():
			ans += max(hash[k] - t, 0)
		R.append(ans)
	for r in R:
		print(r)


from collections import Counter
t = input()
for x in range(0, int(t)):
	(n, q) = map(int, input().split())
	s = input()
	d = Counter(s)
	for i in range(q):
		count = 0
		m = int(input())
		for j in d.values():
			if j > m:
				count += j - m
		print(count)


from collections import Counter
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	S = input().strip()
	S = list(S)
	dct = Counter(S)
	for i101 in range(Q):
		C = int(input())
		pending = 0
		for i in dct.values():
			if i > C:
				pending += i - C
		print(pending)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = input()
	temp = Counter(s)
	res = 0
	for i in range(q):
		c = int(input())
		for j in temp:
			if temp[j] > c:
				res += abs(temp[j] - c)
		print(res)
		res = 0


from collections import Counter
for t in range(int(input())):
	(n, q) = [int(i) for i in input().split(' ')]
	s = input()
	count = list(dict(Counter(s)).values())
	for i in range(q):
		c = int(input())
		penQ = 0
		for i in count:
			if i > c:
				penQ += i - c
		print(penQ)


for tc in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	for j in range(q):
		a = 0
		c = int(input())
		for k in d.values():
			if k > c:
				a += k - c
		print(a)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	l = input()
	l1 = {}
	q1 = []
	for j in range(q):
		q1.append(int(input()))
	for j in l:
		l1.update({j: l.count(j)})
	for k in range(q):
		c = 0
		for j in l1.values():
			if j > q1[k]:
				c += j - q1[k]
			else:
				continue
		print(c)


T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	S = input()
	D = {}
	for x in S:
		if x in D:
			D[x] += 1
		else:
			D[x] = 1
	for _ in range(Q):
		a = 0
		C = int(input())
		for y in D.values():
			if y > C:
				a += y - C
		print(a)


t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for j in range(q):
		ans = 0
		c = int(input())
		for k in d.values():
			if k > c:
				ans += k - c
		print(ans)
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	count = []
	s = list(s)
	s1 = list(set(s))
	for i in s1:
		count.append(s.count(i))
	c = []
	for i in range(q):
		a = int(input())
		c.append(a)
		ans = 0
		for i in count:
			if i > a:
				ans += abs(i - a)
		print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	s = Counter(s)
	while q > 0:
		c = 0
		m = int(input())
		for (k, v) in s.items():
			if v > m:
				c += abs(v - m)
		print(c)
		q -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	w = input()
	d = {}
	for i in w:
		d[i] = d.get(i, 0) + 1
	for i in range(q):
		p = 0
		c = int(input())
		for v in d.values():
			if v > c:
				p += v - c
		print(p)


def main():
	try:
		n = int(input())
		while n > 0:
			(a, b) = map(int, input().split())
			s = list(input())
			freq = [0] * 26
			for ele in s:
				freq[ord(ele) - 97] += 1
			for i in range(b):
				m = int(input())
				count = 0
				for j in range(26):
					if freq[j] > m:
						count += freq[j] - m
				print(count)
			n = n - 1
	except:
		return
main()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	d = {}
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in range(b):
		s1 = 0
		t = int(input())
		for i in d:
			if d[i] > t:
				s1 += d[i] - t
		print(s1)


from collections import Counter as co
for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	query = [int(input()) for i in range(q)]
	dic = dict(co(s))
	for i in query:
		count = 0
		for (key, value) in dic.items():
			if value > i:
				count += value - i
		print(count)


T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	S = input()
	Z = [0 for i in range(26)]
	for i in S:
		Z[ord(i) - 97] = Z[ord(i) - 97] + 1
	for i in range(Q):
		C = int(input())
		ql = 0
		for j in Z:
			ql = ql + max(j - C, 0)
		print(ql)


from sys import stdin
from collections import Counter
for _ in range(int(stdin.readline())):
	(n, q) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	f = Counter(s)
	for _ in range(q):
		c = int(stdin.readline())
		t = sum((max(0, f[k] - c) for k in f))
		print(t)


t = int(input())
for i in range(t):
	n_q = input().split()
	n = int(n_q[0])
	q = int(n_q[1])
	ip = input()
	d = dict()
	for i in ip:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	for k in range(q):
		c = int(input())
		sum = 0
		for val in d.values():
			if val > c:
				sum = sum + val - c
		print(sum)