One day, Vogons wanted to build a new hyperspace highway through a distant system with $n$ planets. The $i$-th planet is on the orbit $a_i$, there could be multiple planets on the same orbit. It's a pity that all the planets are on the way and need to be destructed.

Vogons have two machines to do that.

The first machine in one operation can destroy any planet at cost of $1$ Triganic Pu.

The second machine in one operation can destroy all planets on a single orbit in this system at the cost of $c$ Triganic Pus.

Vogons can use each machine as many times as they want.

Vogons are very greedy, so they want to destroy all planets with minimum amount of money spent. Can you help them to know the minimum cost of this project?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Then the test cases follow.

Each test case consists of two lines.

The first line contains two integers $n$ and $c$ ($1 \le n, c \le 100$) — the number of planets and the cost of the second machine usage.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the orbit of the $i$-th planet.


-----Output-----

For each test case print a single integer — the minimum cost of destroying all planets.


-----Examples-----

Input
4
10 1
2 1 4 5 2 4 5 5 1 2
5 2
3 2 1 2 2
2 2
1 1
2 2
1 2
Output
4
4
2
2
Input
1
1 100
1
Output
1


-----Note-----

In the first test case, the cost of using both machines is the same, so you can always use the second one and destroy all planets in orbit $1$, all planets in orbit $2$, all planets in orbit $4$, all planets in orbit $5$.

In the second test case, it is advantageous to use the second machine for $2$ Triganic Pus to destroy all the planets in orbit $2$, then destroy the remaining two planets using the first machine.

In the third test case, you can use the first machine twice or the second machine once.

In the fourth test case, it is advantageous to use the first machine twice.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	arr = [int(j) for j in input().split()]
	freq = [0] * 101
	for x in arr:
		freq[x] += 1
	ans = 0
	for x in freq:
		ans += min(x, c)
	print(ans)


import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
	(n, m) = map(int, input().split())
	cnt = [0] * 111
	data = list(map(int, input().split()))
	for i in data:
		cnt[i] += 1
	ans = 0
	for i in range(101):
		ans += min(m, cnt[i])
	print(ans)
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	lis = list(map(int, input().split()))
	ans = 0
	di = dict()
	for i in lis:
		di[i] = di.get(i, 0) + 1
	for i in di:
		val = di[i]
		val = min(val, c)
		ans += val
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = defaultdict(int)
	for x in l:
		d[x] += 1
	ans = 0
	for x in d.values():
		if x > c:
			ans += c
		else:
			ans += x
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	x = Counter(arr)
	ans = 0
	for i in x:
		if x[i] >= c:
			ans += c
		else:
			ans += x[i]
	print(ans)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = [0] * 101
	for i in range(n):
		p[arr[i]] += 1
	ans = 0
	for i in range(1, 101):
		ans += min(p[i], c)
	print(ans)


t = int(input())
for ttt in range(t):
	(n, c) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	cnt = [0] * 101
	for i in a:
		cnt[i] += 1
	ans = 0
	for cc in cnt:
		if cc > c:
			ans += c
		else:
			ans += cc
	print(ans)


t = int(input())
for ncase in range(1, t + 1):
	(n, c) = [int(s) for s in input().split(' ')]
	a = [int(s) for s in input().split(' ')]
	d = {}
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = 0
	for orbi in d:
		if d[orbi] >= c:
			ans += c
		else:
			ans += d[orbi]
	print(ans)


from collections import defaultdict, Counter

def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	for (x, y) in Counter(A).items():
		ans += min(m, y)
	print(ans)
for _ in range(int(input())):
	solve()


for bla in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	arr = [0] * 105
	for i in a:
		arr[i] += 1
	cost = 0
	for i in arr:
		if i > c:
			cost += c
		else:
			cost += i
	print(cost)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	cnt = 0
	for i in d:
		if d[i] < c:
			cnt += d[i]
		else:
			cnt += c
	print(cnt)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	count = 1
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			total += min(count, c)
			count = 1
		else:
			count += 1
	total += min(count, c)
	print(total)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	k = 1
	cost = 0
	if len(a) == 1:
		print(1)
	else:
		for i in range(1, len(a)):
			if a[i - 1] == a[i]:
				k += 1
			else:
				if k > c:
					cost += c
				else:
					cost += k
				k = 1
		if k > c:
			cost += c
		else:
			cost += k
		print(cost)


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split(' '))
	arr = [int(j) for j in input().split()]
	d = {}
	res = 0
	for i in arr:
		if i not in d:
			d[i] = 0
		d[i] += 1
	for i in d.keys():
		if d[i] >= c:
			res += c
		else:
			res += d[i]
	print(res)


t = int(input())
while t != 0:
	(n, c) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	dic = {}
	ans = 0
	for num in arr:
		if num not in dic.keys():
			dic[num] = 0
		dic[num] += 1
	for value in dic.values():
		if value <= c:
			ans += value
		else:
			ans += c
	print(ans)
	t -= 1


def one():
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	d = [0] * 101
	for e in a:
		d[e] += 1
	s = 0
	for i in range(len(d)):
		s += min(d[i], c)
	print(s)
t = int(input())
for i in range(t):
	one()


from collections import Counter
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	f = Counter(l)
	print(sum((min(v, c) for v in f.values())))


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

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

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	(n, c) = values()
	l = values()
	tot = 0
	cnt = collections.Counter(l)
	for i in cnt:
		tot += min(cnt[i], c)
	print(tot)
for i in range(inp()):
	solve()


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	c = inputs[1]
	list2 = [int(num) for num in input().split()]
	dict1 = {}
	for i in range(0, n):
		if list2[i] not in dict1:
			dict1[list2[i]] = 0
		dict1[list2[i]] += 1
	cost = 0
	for key in dict1:
		if dict1[key] <= c:
			cost += dict1[key]
		else:
			cost += c
	print(cost)


t = int(input())
for _ in range(t):
	(n, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	cost = 0
	for i in d:
		if d[i] < c:
			cost += d[i]
		else:
			cost += c
	print(cost)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	di = {}
	for x in l:
		if x in di:
			di[x] = di[x] + 1
		else:
			di[x] = 1
	z = 0
	for x in di:
		z += min(di[x], c)
	print(z)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	z = [0] * 101
	for i in a:
		z[i] += 1
	b = [p if i > p else i for i in z]
	s = sum(b)
	print(s)


import collections

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n, c) = inp_arr()
	a = inp_arr()
	mp = collections.defaultdict(int)
	for x in a:
		mp[x] += 1
	cost = 0
	for x in mp:
		cost += min(c, mp[x])
	print(cost)
tt = inp_int()
for t in range(tt):
	solve()


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * 101
	s = n
	for x in a:
		b[x - 1] += 1
	for x in b:
		if x > c:
			s -= x - c
	print(s)


from collections import Counter
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	d = Counter(l)
	ans = 0
	for i in d.values():
		ans += min(i, c)
	print(ans)


import sys
from collections import Counter
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def solve():
	(n, c) = inlt()
	a = sorted(inlt())
	cntr = Counter(a)
	ans = 0
	for (k, v) in cntr.items():
		opt_1 = v
		opt_2 = c
		ans += min(opt_1, opt_2)
	return ans
t = inp()
for i in range(t):
	ans = solve()
	print(ans)


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def yesno(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		(n, c) = get_ints()
		ls = get_ls()
		ans = 0
		d = {}
		for i in ls:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for i in d.values():
			if i == 1:
				ans += 1
			else:
				ans += min(i, c)
		print(ans)
main()


from sys import stdin, stdout

def main():
	t = int(stdin.readline())
	for i in range(t):
		(n, c) = map(int, stdin.readline().split())
		a = list(map(int, stdin.readline().split()))
		dic = {}
		for num in a:
			if num in dic:
				dic[num] += 1
			else:
				dic[num] = 1
		cost = 0
		for key in dic:
			if dic[key] > c:
				cost += c
			else:
				cost += dic[key]
		print(cost)
main()


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, c) = map(int, input().split())
	A = list(map(int, input().split()))
	net = collections.Counter(A)
	ans = 0
	for a in net:
		k = net[a]
		ans += min(k, c)
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	dic = {}
	z = set(a)
	cost = 0
	for i in a:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	for i in z:
		if c > dic[i]:
			cost += dic[i]
		else:
			cost += c
	print(cost)


from collections import defaultdict
t = int(input())
for _ in range(t):
	planets = defaultdict(int)
	count = 0
	(n, c) = map(int, input().split())
	p = list(map(int, input().split()))
	for i in p:
		planets[i] += 1
	for (o, ps) in planets.items():
		if ps >= c:
			count += c
		else:
			count += ps
	print(count)


def main():
	n_tests = int(input())
	for _ in range(n_tests):
		(n, c) = list(map(int, input().split(' ')))
		elems = list(map(int, input().split(' ')))
		counter = {}
		for x in elems:
			if x not in counter:
				counter[x] = 0
			counter[x] += 1
		cost = 0
		for (orbit, cnt) in reversed(sorted(counter.items(), key=lambda x: x[1])):
			cost += min(cnt, c)
		print(cost)
main()


t = eval(input())
for i in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	k = {}
	sum = 0
	for i in a:
		if i not in k:
			k[i] = 1
		else:
			k[i] += 1
	for i in k:
		if k[i] > c:
			sum += c
		else:
			sum += k[i]
	print(sum)


for _ in range(int(input())):
	(n, c) = [int(x) for x in input().split(' ')]
	arr = [int(x) for x in input().split(' ')]
	mp = [0 for i in range(101)]
	for val in arr:
		mp[val] += 1
	ans = 0
	for i in range(101):
		if mp[i] > c:
			ans += c
		else:
			ans += mp[i]
	print(ans)


k = int(input())
for i in range(k):
	summa = 0
	(n, c) = map(int, input().split())
	a = input().split()
	d = {}
	for i in a:
		if not d.get(i):
			d[i] = 1
		else:
			d[i] += 1
	for i in d.values():
		if i < c:
			summa += i
		else:
			summa += c
	print(summa)


cases = int(input())
for i in range(cases):
	(n, c) = input().split()
	n = int(n)
	c = int(c)
	orb = {}
	temp = input().split()
	for j in temp:
		j = int(j)
		orb[j] = orb.get(j, 0) + 1
	total = 0
	for (k, v) in orb.items():
		total += min(v, c)
	print(total)


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	lis = list(map(int, input().split()))
	setlis = set(lis)
	setlis = list(setlis)
	countlis = []
	for j in setlis:
		countlis.append(lis.count(j))
	cost = 0
	for j in countlis:
		one = j
		if one < c:
			cost += one
		else:
			cost += c
	print(cost)


for i in range(int(input())):
	(n, c) = map(int, input().split())
	orbits = [x for x in input().split()]
	count_dict = dict()
	ans = 0
	for orbit in orbits:
		if orbit in count_dict:
			count_dict[orbit] += 1
		else:
			count_dict[orbit] = 1
	for vals in count_dict.values():
		if vals > c:
			ans += c
		else:
			ans += vals
	print(ans)


t = int(input())
while t:
	(n, c) = map(int, input().split())
	orb = list(map(int, input().split()))
	ans = 0
	d = {}
	for ele in orb:
		if ele not in d:
			d[ele] = 1
		else:
			d[ele] += 1
	for k in d:
		ans += min(d[k] * 1, c)
	print(ans)
	t -= 1


def solve():
	[n, c] = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	d = {}
	for p in a:
		if p in d:
			d[p] += 1
		else:
			d[p] = 1
	cost = 0
	for k in d:
		cost += min(c, d[k])
	print(cost)
for _ in range(int(input())):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	cnt = defaultdict(int)
	res = 0
	arr = list(map(int, input().split()))
	for v in arr:
		cnt[v] += 1
	for (i, v) in cnt.items():
		if v >= c:
			res += c
		else:
			res += v
	print(res)


for _ in range(int(input())):
	(n, c) = input().split(' ')
	n = int(n)
	c = int(c)
	d = {}
	a = input().split(' ')
	ans = 0
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for (key, val) in d.items():
		if val > c:
			ans += c
		else:
			ans += val
	print(ans)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	a = [i for i in list(input().split())]
	b = set(a)
	res = 0
	for x in b:
		k = a.count(x)
		if k > c:
			res += c
		else:
			res += k
	print(res)


from sys import stdin, stdout

def solve():
	(n, c) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	freq = {}
	for o in a:
		freq[o] = 1 + freq.get(o, 0)
	cost = 0
	for n in freq.values():
		cost += min(c, n)
	print(cost)

def main():
	t = int(stdin.readline())
	for i in range(t):
		solve()
main()


ntestcases = int(input())
for t in range(ntestcases):
	(nPlanets, machineCost) = map(int, input().split(' '))
	minCost = nPlanets
	planetsPerOrbit = {}
	orbits = list(map(int, input().split(' ')))
	for orbit in orbits:
		if orbit not in planetsPerOrbit:
			planetsPerOrbit[orbit] = 0
		planetsPerOrbit[orbit] += 1
		if planetsPerOrbit[orbit] > machineCost:
			minCost -= 1
	print(minCost)


t = int(input())
while t != 0:
	t -= 1
	(n, c) = input().split()
	n = int(n)
	c = int(c)
	arr = input().split()
	dict = {}
	for i in range(len(arr)):
		arr[i] = int(arr[i])
		if arr[i] in dict.keys():
			dict[arr[i]] += 1
		else:
			dict[arr[i]] = 1
	ans = 0
	for i in dict.keys():
		if dict[i] > c:
			ans += c
		else:
			ans += dict[i]
	print(ans)


t = int(input())
ans = []
for _ in range(t):
	(n, c) = map(int, input().split())
	plan = list(map(int, input().split()))
	dick = {}
	now = 0
	for e in plan:
		dick[e] = dick.get(e, 0) + 1
	for e in dick.keys():
		if dick[e] > c:
			now += c
		else:
			now += dick[e]
	ans.append(str(now))
print('\n'.join(ans))


numCases = int(input())
outputArray = []
for i in range(numCases):
	arrayN = list(map(int, input().split(' ')))
	c = arrayN[1]
	dict = {}
	sum = 0
	arrayPlanet = list(map(int, input().split(' ')))
	for j in arrayPlanet:
		dict[j] = 1 + dict.get(j, 0)
	for j in dict:
		if dict[j] > 1:
			if dict[j] > c:
				sum += c
			else:
				sum += dict[j]
		else:
			sum += 1
	outputArray.append(sum)
for i in outputArray:
	print(i)


for _ in range(int(input())):
	[n, c] = list(map(int, input().split()))
	a = input().split()
	di = dict()
	for i in a:
		if i in di:
			di[i] += 1
		else:
			di[i] = 1
	val = 0
	for i in di.values():
		if i > c:
			val += c
		else:
			val += i
	print(val)


ad = int(input())
for i in range(ad):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i]] = 0
	for i in range(n):
		d[l[i]] += 1
	r = 0
	for i in d:
		if d[i] > c:
			r += c
		else:
			r += d[i]
	print(r)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	q = 0
	a = list(map(int, input().split()[:n]))
	c = {}
	for i in a:
		if i in c:
			c[i] += 1
		else:
			c[i] = 1
	m = list(c.values())
	for i in m:
		if i < p:
			q += i
		else:
			q += p
	print(q)


for x in range(int(input())):
	(n, c) = map(int, input().split())
	fa = [0] * 200
	res = 0
	arr = list(map(int, input().split()))
	s = []
	for i in arr:
		fa[i] += 1
		if i not in s:
			s.append(i)
	for i in s:
		res += min(fa[i], c)
	print(res)


t = int(input())
for i in range(t):
	l0 = input().split()
	n = int(l0[0])
	c = int(l0[1])
	l = input().split()
	dct = {}
	cost = 0
	rem = n
	for j in l:
		a = int(j)
		if j in dct:
			dct[j] += 1
		else:
			dct[j] = 1
	for k in dct:
		if dct[k] >= c:
			cost += c
			rem = rem - dct[k]
	for m in range(rem):
		cost += 1
	print(cost)


def func():
	(N, C) = list(map(int, input().split()))
	Planets = list(map(int, input().split()))
	vals_dics = {}
	for p in Planets:
		if p not in vals_dics:
			vals_dics[p] = 0
		vals_dics[p] += 1
	ret = 0
	for p in vals_dics:
		if vals_dics[p] > C:
			ret += C
		else:
			ret += vals_dics[p]
	print(ret)
n_tests = int(input())
for i in range(n_tests):
	func()


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	count = 0
	for i in range(len(arr)):
		if arr[i] in d:
			d[arr[i]] += 1
		else:
			d[arr[i]] = 1
	for (k, v) in d.items():
		ans = min(v, c)
		count += ans
	print(count)


for i in range(int(input())):
	nc = [int(x) for x in input().split()]
	n = nc[0]
	c = nc[1]
	a = [int(x) for x in input().split()]
	d = {}
	for num in a:
		try:
			d[num] += 1
		except:
			d[num] = 1
	total = 0
	for (ring, planets) in d.items():
		if c < planets:
			total += c
		else:
			total += planets
	print(total)


import sys
from collections import Counter

def run():
	(n, c) = tuple(map(int, sys.stdin.readline().split()))
	planets = Counter(map(int, sys.stdin.readline().split()))
	cost = 0
	for a in planets.values():
		cost += min(a, c)
	print(cost)
t = int(input())
for _ in range(t):
	run()


n = int(input())
first_gun_cost = 1
for i in range(n):
	price = 0
	orbits = dict()
	(planets_num, second_gun_cost) = [int(i) for i in input().split()]
	planets = input().split()
	for planet in planets:
		if planet not in orbits:
			orbits[planet] = 1
		else:
			orbits[planet] += 1
	for key in orbits:
		if orbits[key] >= second_gun_cost:
			price += second_gun_cost
		else:
			price += orbits[key]
	print(price)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	v = list(map(int, input().split()))
	v1 = [0] * 101
	for j in range(x):
		v1[v[j]] += 1
	r = 0
	for j in range(101):
		if v1[j] < y:
			r += v1[j]
		else:
			r += y
	print(r)


m = int(input())
final = []
for i in range(m):
	nc = input()
	n = int(nc.split()[0])
	c = int(nc.split()[1])
	a = list(map(int, input().split()))
	a.sort()
	dict1 = {}
	cost = 0
	for i in a:
		if i not in dict1:
			dict1[i] = 1
		else:
			dict1[i] += 1
	for i in dict1:
		if dict1[i] >= c:
			cost += c
		else:
			cost += dict1[i]
	final.append(cost)
for i in final:
	print(i)


t = int(input())
result = []
for i in range(t):
	(n, c) = list(map(int, input().split(' ')))
	countt = [0 for i in range(101)]
	orbit = input().split(' ')
	sum = 0
	for j in orbit:
		countt[int(j)] = countt[int(j)] + 1
	for j in countt:
		sum += min(j, c)
	result.append(sum)
for i in result:
	print(i)


t = int(input())
for i in range(t):
	(n, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mapa = {}
	for k in range(n):
		mapa[a[k]] = 0
	for j in range(n):
		mapa[a[j]] = mapa[a[j]] + 1
	ans = 0
	for (items, value) in mapa.items():
		ans = ans + min(value, c)
	print(ans)


import sys

def solution():
	line_num = 0
	line1 = []
	line2 = []
	for line in sys.stdin:
		if line_num == 0:
			line_num += 1
			continue
		if line_num % 2 == 1:
			line1 = [int(x) for x in line.strip().split()]
			if line1[0] == 0:
				print(0)
				return
		else:
			line2 = [int(x) for x in line.strip().split()]
			cost = line1[1]
			num = line1[0]
			dic = {}
			for elem in line2:
				if elem in dic:
					dic[elem] += 1
				else:
					dic[elem] = 1
			res = 0
			for i in dic.values():
				res += min(cost, i)
			print(res)
		line_num += 1
solution()


from collections import Counter

def f(n, c, a):
	o_and_p = Counter(a)
	if c == 1:
		res = len(o_and_p)
	else:
		res = 0
		for i in o_and_p.values():
			if i >= c:
				res += c
			else:
				res += i
	print(res)
t = int(input())
while t:
	t -= 1
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	f(n, c, a)


import sys
m = int(sys.stdin.readline())
for i in range(m):
	w = sys.stdin.readline().replace('\n', '').split(' ')
	a = sys.stdin.readline().replace('\n', '').split(' ')
	c = int(w[1])
	ans = 0
	r = set()
	for q in range(int(w[0])):
		r.add(int(a[q]))
	u = max(r) + 1
	s = [0] * u
	for q in range(int(w[0])):
		s[int(a[q])] += 1
	for q in range(u):
		ans += min(s[q], c)
	print(ans)


import sys
t = int(input())
for i in range(t):
	(n, c) = list(map(int, input().strip().split()))
	a = list(map(int, input().strip().split()))
	count = {}
	for orbit in a:
		if orbit in count:
			count[orbit] += 1
		else:
			count[orbit] = 1
	cost = 0
	for orbit in count:
		planets = count[orbit]
		if c < planets:
			cost += c
		else:
			cost += planets
	print(cost)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	hashmap = {}
	for i in range(n):
		if a[i] not in hashmap:
			hashmap[a[i]] = 0
		hashmap[a[i]] += 1
	ans = 0
	for elem in hashmap.values():
		if elem > c:
			ans += c
		else:
			ans += elem
	print(ans)


t = int(input())

def main():
	for q in range(t):
		DICTIONARY = {}
		(NUMS, GUESS) = map(int, input().split())
		ARRAY = list(map(int, input().split()))
		for ITER in ARRAY:
			if not ITER in DICTIONARY:
				DICTIONARY[ITER] = 0
			DICTIONARY[ITER] = DICTIONARY[ITER] + 1
		RES = 0
		for i in DICTIONARY.keys():
			if DICTIONARY[i] >= GUESS:
				RES = RES + GUESS
			else:
				RES = RES + DICTIONARY[i]
		print(RES)
main()


from collections import Counter
ans = []
t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	count = Counter(list(map(int, input().split()[:n])))
	cost = 0
	for (key, item) in count.items():
		cost += min(c, item)
	ans.append(cost)
for a in ans:
	print(a)


t = int(input())
for i in range(t):
	summ = 0
	counter = 1
	nc = input()
	ai = input()
	b = nc.split()
	f = ai.split()
	n = int(b[0])
	c = int(b[1])
	if n == 1:
		print(1)
		continue
	f.sort()
	for j in range(n - 1):
		if f[j] == f[j + 1]:
			counter = counter + 1
		elif counter > c:
			summ = summ + c
			counter = 1
		else:
			summ = summ + counter
			counter = 1
	if counter != 1:
		if counter > c:
			summ = summ + c
			counter = 1
		else:
			summ = summ + counter
			counter = 1
	else:
		summ = summ + 1
	print(summ)


def get_cost(n, c, A):
	dict_all = {}
	for i in range(n):
		if A[i] not in dict_all.keys():
			dict_all[A[i]] = 1
		else:
			dict_all[A[i]] += 1
	cost = 0
	for key in dict_all.keys():
		if dict_all[key] < c:
			cost += dict_all[key]
		else:
			cost += c
	return cost
n = int(input())
total_input = []
for _ in range(n):
	n_c = list(map(int, input().split()))
	Ai = list(map(int, input().split()))
	total_input.append([n_c, Ai])
for i in range(n):
	print(get_cost(total_input[i][0][0], total_input[i][0][1], total_input[i][1]))


for tests in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		try:
			d[i] += 1
		except:
			d[i] = 1
	cost = 0
	for i in d:
		if d[i] > c:
			cost += c
		else:
			cost += d[i]
	print(cost)


t = int(input())
res = []
for _ in range(t):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	cost = 0
	for k in s:
		cc = l.count(k)
		if cc >= c:
			cost += c
		else:
			cost += cc
	res.append(str(cost))
print('\n'.join(res))


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 0
	for i in d:
		if d[i] == 1:
			ans += 1
		else:
			ans += min(d[i], c)
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, c) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	if c == 1:
		print(len(list(set(a))))
	else:
		cost = 0
		_dict = dict(Counter(a))
		for key in _dict:
			if _dict[key] > c:
				cost += c
			else:
				cost += _dict[key]
		print(cost)


tests = int(input())
for cases in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dict1 = {}
	sum = 0
	for ele in arr:
		if ele not in dict1:
			dict1[ele] = 1
		else:
			dict1[ele] = dict1[ele] + 1
	for ele in dict1:
		if dict1[ele] > k:
			sum = sum + k
		else:
			sum = sum + dict1[ele]
	print(sum)


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	d = dict()
	t = 0
	for j in l:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	for j in d.values():
		if j > c:
			t += c
		else:
			t += j
	print(t)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	orbit = list(map(int, input().split()))
	orbit.sort()
	orbit.append(0)
	b = []
	count = 0
	cost = 0
	for i in range(n):
		if orbit[i] == orbit[i + 1]:
			count += 1
		else:
			b.append(count + 1)
			count = 0
	for i in b:
		if i < c:
			cost += i
		else:
			cost += c
	print(cost)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	d = dict()
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	tot = 0
	for i in d:
		if d[i] > c:
			tot += c
		else:
			tot += d[i]
	print(tot)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	cos = 0
	res = 1
	f = l[0]
	for i in range(1, n):
		if l[i] == f:
			res = res + 1
		else:
			cos = cos + min(res, c)
			res = 1
			f = l[i]
	cos = cos + min(res, c)
	print(cos)


def get_min_cost(n, c, planets):
	orbit_count = {}
	for i in range(n):
		orbit_count[planets[i]] = orbit_count.get(planets[i], 0) + 1
	result = 0
	for (orbit, count) in orbit_count.items():
		if count <= c:
			result += count
		if count > c:
			result += c
	return result
t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	planets = list(map(int, input().split()))
	print(get_min_cost(n, c, planets))


t = int(input())
while t > 0:
	infoList = list(map(int, input().split()))
	planetList = list(map(int, input().split()))
	n = infoList[0]
	c = infoList[1]
	planetList.sort()
	cost = 0
	cnt = 1
	for i in range(0, len(planetList)):
		if i == 0:
			continue
		if planetList[i - 1] != planetList[i]:
			if c >= 1 * cnt:
				cost += cnt
			else:
				cost += c
			cnt = 1
			continue
		cnt += 1
	if c >= 1 * cnt:
		cost += cnt
	else:
		cost += c
	if len(list(set(planetList))) == 1:
		if c >= 1 * len(planetList):
			cost = len(planetList)
		else:
			cost = c
	print(cost)
	t -= 1


def destroy_planets():
	t = int(input())
	for _ in range(t):
		(n, cost) = map(int, input().split())
		dupes = list(map(int, input().split()))[:n]
		dict = {}
		for i in range(len(dupes)):
			if dupes[i] not in dict:
				dict[dupes[i]] = 0
			dict[dupes[i]] += 1
		total_cost = 0
		for (key, value) in dict.items():
			initial_cost = min(value * 1, cost)
			total_cost += initial_cost
		print(total_cost)
destroy_planets()


from array import *
t = int(input())
ans = 0
num = [0 for x in range(101)]
for i in range(t):
	ans = 0
	num = [0 for x in range(101)]
	(n, c) = map(int, input().split())
	a = input().split()
	for k in range(len(a)):
		num[int(a[k])] += 1
	for k in range(101):
		if num[k] > c:
			ans += c
		elif num[k] > 0:
			ans += num[k]
		else:
			ans = ans + 0
	print(ans)


t = int(input())
for test in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	c = inp[1]
	a = list(map(int, input().split()))
	num_list = [0] * 101
	for i in a:
		num_list[i] += 1
	score = 0
	for i in num_list:
		if i > c:
			score += c
		else:
			score += i
	print(score)


n = int(input())
for _ in range(n):
	(n_planets, x) = map(int, input().split(' '))
	Data = list(map(int, input().split(' ')))
	Data.sort()
	cost1 = 1
	cost = 0
	orbit = Data[0]
	for i in range(1, len(Data)):
		if Data[i] == orbit:
			cost1 += 1
		else:
			if cost1 < x:
				cost += cost1
			else:
				cost += x
			cost1 = 1
			orbit = Data[i]
	if cost1 < x:
		cost += cost1
	else:
		cost += x
	print(cost)


def ans():
	t = int(input())
	for i in range(t):
		(n, c) = input().split()
		n = int(n)
		c = int(c)
		arrNums = list(map(int, input().split()))
		s = {}
		for i in arrNums:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		solution = 0
		for (k, v) in s.items():
			solution += min(c, v)
		print(solution)
ans()


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	A = [int(x) for x in input().split()]
	B = {}
	Sum = 0
	for i in A:
		if i in B:
			B[i] += 1
		else:
			B[i] = 1
	for i in B.values():
		if i < c:
			Sum += i
		else:
			Sum += c
	print(Sum)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lst = [int(i) for i in input().split()]
	d = {}
	for i in lst:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	c = 0
	for i in d.keys():
		c += min(d[i], k)
	print(c)


t = int(input())
while t:
	t -= 1
	(n, c) = map(int, input().split())
	li = list(map(int, input().split()))
	d = {}
	for i in li:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = 0
	for (i, j) in d.items():
		if j > c:
			ans += c
		else:
			ans += j
	print(ans)


n = int(input())
while n:
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	count = 0
	for value in d.values():
		if value == 1:
			count += 1
		elif value >= b:
			count += b
		else:
			count += value
	print(count)
	n -= 1


t = int(input())
for i in range(t):
	(n, c) = input().split()
	c = int(c)
	l = list()
	l = input().split()
	s = set(l)
	cost = 0
	for j in s:
		cost = cost + min(l.count(j), c)
	print(cost)


for _ in range(int(input())):
	(len1, c) = map(int, input().split())
	list1 = list(map(int, input().rstrip().split()))
	dict1 = {}
	count = 0
	for i in range(len1):
		if list1[i] not in dict1:
			dict1[list1[i]] = 1
		else:
			dict1[list1[i]] += 1
	for i in dict1:
		count += min(dict1[i], c)
	print(count)


t = int(input())
for ind in range(t):
	(n0, c0) = input().split()
	n = int(n0)
	c = int(c0)
	arr = list(map(int, input().strip().split()))[:n]
	arr.sort()
	cost = 1
	count = 1
	for i in range(1, n):
		if arr[i] == arr[i - 1] and count < c:
			cost += 1
			count += 1
		elif arr[i] == arr[i - 1] and count >= c:
			continue
		else:
			count = 1
			cost += 1
	print(cost)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	s = [0] * 101
	for i in range(n):
		s[a[i]] += 1
	ans = 0
	for i in range(len(s)):
		ans += min(s[i], c)
	print(ans)


def inp():
	return int(input())

def strng():
	return input().strip()

def jn(x, l):
	return x.join(map(str, l))

def strl():
	return list(input().strip())

def mul():
	return map(int, input().strip().split())

def mulf():
	return map(float, input().strip().split())

def seq():
	return list(map(int, input().strip().split()))

def ceil(x):
	return int(x) if x == int(x) else int(x) + 1

def ceildiv(x, d):
	return x // d if x % d == 0 else x // d + 1
for i in range(inp()):
	(a, b) = mul()
	lst = seq()
	d = {}
	for i in lst:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	cnt = 0
	for j in d:
		if d[j] < b:
			cnt += d[j]
		else:
			cnt += b
	print(cnt)


t = int(input())
for i in range(t):
	(planet, c) = [int(value) for value in input().split()]
	orbit = [int(value) for value in input().split()]
	D = {}
	cost = 0
	for i in orbit:
		if i in D.keys():
			D[i] += 1
		else:
			D[i] = 1
	for (o, p) in D.items():
		if c / p >= 1:
			cost += p
		else:
			cost += c
	print(cost)