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

Chef went to Australia and saw the destruction caused by bushfires, which made him sad, so he decided to help the animals by feeding them fruits. First, he went to purchase fruits from Pintu.

Pintu sells $M$ different types of fruits (numbered $1$ through $M$). He sells them in $N$ baskets (numbered $1$ through $N$), where for each valid $i$, the $i$-th basket costs $P_{i}$ and it contains fruits of type $F_{i}$. Chef does not have too much money, so he cannot afford to buy everything; instead, he wants to choose one of the $M$ available types and purchase all the baskets containing fruits of that type.

Help Chef choose the type of fruit to buy such that he buys at least one basket and the total cost of the baskets he buys is the smallest possible.

------  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 $M$.
The second line contains $N$ space-separated integers $F_{1}, F_{2}, \ldots, F_{N}$.
The third line contains $N$ space-separated integers $P_{1}, P_{2}, \ldots, P_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum price Chef must pay.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ M, N ≤ 50$
$1 ≤ F_{i} ≤ M$ for each valid $i$
$0 ≤ P_{i} ≤ 50$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $M = 2$

Subtask #2 (70 points): original constraints

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

6 4

1 2 3 3 2 2

7 3 9 1 1 1
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Example case 1:
- The sum of all baskets with fruits of type $1$ is $7$.
- The sum of all baskets with fruits of type $2$ is $5$.
- The sum of all baskets with fruits of type $3$ is $10$.
- The sum of all baskets with fruits of type $4$ is $0$ because there are no such baskets.

Chef can only choose fruits of type $1$, $2$ or $3$. Therefore, the minimum price he has to pay is $5$.

Difficulty: EASY
Tags: Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
for i in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if f[i] not in d:
			d[f[i]] = p[i]
		else:
			d[f[i]] = d[f[i]] + p[i]
	m = 100000
	for i in d.values():
		if i < m:
			m = i
	print(m)


t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	l1 = [int(i) for i in input().split()]
	l2 = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		if l1[i] not in d:
			d[l1[i]] = l2[i]
		else:
			d[l1[i]] = d[l1[i]] + l2[i]
	m = 100000
	for i in d.values():
		if i <= m:
			m = i
	print(m)


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = {}
	for i in range(n):
		if a[i] in c:
			c[a[i]] += b[i]
		else:
			c[a[i]] = b[i]
	d = list(c.values())
	d.sort()
	print(d[0])


try:
	t = int(input())
	for i in range(t):
		(a, b) = map(int, input().split())
		f = list(map(int, input().split()))
		p = list(map(int, input().split()))
		d = {}
		for i in range(a):
			if f[i] not in d:
				d[f[i]] = p[i]
			else:
				d[f[i]] = d[f[i]] + p[i]
		print(min(d.values()))
except:
	pass


for j in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(len(f)):
		if f[i] not in d:
			d[f[i]] = p[i]
		else:
			d[f[i]] += p[i]
	print(min(d.values()))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	Dict = {}
	for j in range(n):
		if f[j] in Dict:
			Dict[f[j]] += p[j]
		else:
			Dict[f[j]] = p[j]
	l = []
	for (key, value) in Dict.items():
		l.append(value)
	l.sort()
	print(l[0])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	price_dict = {}
	for i in range(n):
		t = a[i]
		price_dict[t] = price_dict.get(t, 0) + b[i]
	print(min(price_dict.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f1 = list(map(int, input().split()))
	p1 = list(map(int, input().split()))
	d1 = {}
	for i in range(n):
		if d1.get(f1[i]) == None:
			d1[f1[i]] = p1[i]
		else:
			d1[f1[i]] = d1[f1[i]] + p1[i]
	ans = 0
	minimum = 1000000
	for (key, value) in d1.items():
		if value < minimum:
			ans = key
			minimum = value
	print(minimum)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	list1 = list(map(int, input().split()))
	x = max(list1)
	list3 = list(map(int, input().split()))
	freq = [0] * (x + 1)
	s = 0
	list4 = []
	for i in range(0, len(list1)):
		freq[list1[i]] = freq[list1[i]] + list3[i]
		list4.append(list1[i])
	m = 0
	f = 0
	for i in range(1, len(freq)):
		if i in list4:
			if f == 0:
				m = freq[i]
				f = 1
			elif freq[i] < m:
				m = freq[i]
	print(m)
	t = t - 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[t[i]] = d.get(t[i], 0) + p[i]
	print(min(d.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	dict = {}
	for i in range(n):
		if f[i] not in dict:
			dict[f[i]] = p[i]
		else:
			dict[f[i]] += p[i]
	print(min(dict.values()))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	ans = []
	for i in range(1, m + 1):
		if i in f:
			suma = 0
			for j in range(n):
				if f[j] == i:
					suma += p[j]
			ans.append(suma)
	print(min(ans))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	li1 = list(map(int, input().split()))
	li2 = list(map(int, input().split()))
	d = {}
	for i in range(a):
		if li1[i] not in d.keys():
			d[li1[i]] = li2[i]
		else:
			d[li1[i]] += li2[i]
	print(min(d.values()))


T = int(input())
for i in range(T):
	(N, M) = list(map(int, input().split()))
	fruit = list(map(int, input().split()))
	price = list(map(int, input().split()))
	d = {}
	for n in range(N):
		if fruit[n] not in d:
			d[fruit[n]] = price[n]
		else:
			d[fruit[n]] += price[n]
	print(min(d.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	d = {}
	for i in range(len(f)):
		if f[i] not in d:
			d[f[i]] = p[i]
		else:
			d[f[i]] += p[i]
	print(min(d.values()))


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	costs = {}
	for i in range(n):
		if f[i] in costs:
			costs[f[i]] += p[i]
		else:
			costs[f[i]] = p[i]
	print(min(costs.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	frr = list(map(int, input().split()))
	prr = list(map(int, input().split()))
	ans = {}
	for i in range(n):
		if frr[i] in ans:
			ans[frr[i]] += prr[i]
		else:
			ans[frr[i]] = prr[i]
	print(min(ans.values()))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	memo = {}
	for i in range(n):
		if f[i] in memo:
			memo[f[i]] += p[i]
		else:
			memo[f[i]] = p[i]
	ans = 1000000
	for i in memo:
		if memo[i] < ans:
			ans = memo[i]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	fruits = list(map(int, input().split()))
	costs = list(map(int, input().split()))
	final_costs = []
	for i in range(1, m + 1):
		cost = 0
		for j in range(len(fruits)):
			if fruits[j] == i:
				cost += costs[j]
		if i in fruits:
			final_costs.append(cost)
	if final_costs != []:
		print(min(final_costs))
	else:
		print(-1)


t = int(input())
for __ in range(t):
	(n, m) = [int(i) for i in input().split()]
	f = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	d = {}
	for i in range(n):
		if f[i] in d:
			d[f[i]] += p[i]
		else:
			d[f[i]] = p[i]
	print(min(list(d.values())))


t = int(input())
for r in range(t):
	(a, b) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(a):
		if f[i] not in d:
			d[f[i]] = p[i]
		else:
			d[f[i]] = d[f[i]] + p[i]
	print(min(d.values()))


try:
	t = int(input())
	for r in range(t):
		(m, n) = map(int, input().split())
		f = list(map(int, input().split()))
		p = list(map(int, input().split()))
		d = {}
		for i in range(m):
			if f[i] not in d:
				d[f[i]] = p[i]
			else:
				d[f[i]] = d[f[i]] + p[i]
		print(min(d.values()))
except:
	pass


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = list(map(int, input().split()))
	a = {}
	for i in range(n):
		if l[i] not in a:
			a[l[i]] = s[i]
		else:
			a[l[i]] += s[i]
	x = a.values()
	print(min(x))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	di = {}
	for i in f:
		di[i] = 0
	for (i, j) in zip(f, p):
		di[i] = di[i] + j
	l = list(di.values())
	print(min(l))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	F = list(map(int, input().split()))
	P = list(map(int, input().split()))
	d = {}
	for i in F:
		d[i] = 0
	for (i, j) in zip(F, P):
		d[i] += j
	print(min(list(d.values())))


n = int(input())
for i in range(0, n):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	h = {}
	for i in range(x):
		if l[i] not in h:
			h[l[i]] = m[i]
		else:
			h[l[i]] = h[l[i]] + m[i]
	print(min(h.values()))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	f1 = list(set(f))
	lis = []
	sm = 0
	for i in range(len(f1)):
		for j in range(len(f)):
			if f[j] == f1[i]:
				sm += p[j]
		lis.append(sm)
		sm = 0
	print(min(lis))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arrF = list(map(int, input().split()))
	arrP = list(map(int, input().split()))
	costs = [-1 for _ in range(m)]
	for (f, p) in zip(arrF, arrP):
		if costs[f - 1] == -1:
			costs[f - 1] = 0
		costs[f - 1] += p
	costs = [cost for cost in costs if cost >= 0]
	print(min(costs))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	fruits = list(map(int, input().split(' ')))
	prices = list(map(int, input().split(' ')))
	print(min([sum([p for (f, p) in zip(fruits, prices) if f == m + 1]) for m in range(M) if m + 1 in fruits]))


mapInput = lambda : map(int, input().split())
Linput = lambda : list(mapInput())
for _ in range(int(input())):
	(n, m) = mapInput()
	f = Linput()
	p = Linput()
	dt = {}
	for (index, i) in enumerate(f):
		if i in dt.keys():
			dt[i] += p[index]
		else:
			dt[i] = p[index]
	print(min(dt.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lstf = list(map(int, input().split()))
	lstp = list(map(int, input().split()))
	dt = {}
	for (index, i) in enumerate(lstf):
		if i in dt.keys():
			dt[i] += lstp[index]
		else:
			dt[i] = lstp[index]
	print(min(dt.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	prices = [-1] * 51
	for i in range(n):
		if prices[f[i]] == -1:
			prices[f[i]] = p[i]
		else:
			prices[f[i]] += p[i]
	prices.sort()
	for v in prices:
		if v > -1:
			print(v)
			break


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(len(f)):
		if d.get(f[i]):
			d[f[i]] += p[i]
		else:
			d[f[i]] = p[i]
	print(min(d.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = {}
	for i in range(len(a)):
		if a[i] in c:
			c[a[i]] += b[i]
		else:
			c[a[i]] = b[i]
	print(min(c.values()))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	bu = list(map(int, input().split()))
	co = list(map(int, input().split()))
	d = {}
	for i in range(len(bu)):
		if bu[i] not in d:
			d[bu[i]] = co[i]
		else:
			d[bu[i]] += co[i]
	print(min(d.values()))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	t = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = {}
	for i in range(len(t)):
		if t[i] in d:
			d[t[i]] += c[i]
		else:
			d[t[i]] = c[i]
	print(min(d.values()))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	d = {}
	l = []
	for (x, y) in zip(l1, l2):
		d[x] = d.get(x, 0) + y
	for x in d.values():
		l.append(x)
	print(min(l))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if p[i] in d:
			d[p[i]] += c[i]
		else:
			d[p[i]] = c[i]
	minimum = max(d.values())
	for i in d:
		minimum = min(minimum, d[i])
	print(minimum)


for x in range(int(input())):
	(N, M) = list(map(int, input().split()))
	fruit = list(map(int, input().split()))
	basket = list(map(int, input().split()))
	basket_list = []
	for x in range(N):
		total = 0
		total += basket[x]
		for y in range(N):
			if fruit[x] == fruit[y] and x != y:
				total += basket[y]
			else:
				continue
		basket_list.append(total)
	print(min(basket_list))


for x in range(int(input())):
	(N, M) = list(map(int, input().split()))
	fruit = list(map(int, input().split()))
	basket = list(map(int, input().split()))
	basket_list = []
	for x in range(N):
		total = 0
		total += basket[x]
		for y in range(N):
			if fruit[x] == fruit[y] and x != y:
				total += basket[y]
		basket_list.append(total)
	basket_list.sort()
	print(basket_list[0])


for testcase in range(int(input())):
	(n, m) = map(int, input().split())
	fruits = list(map(int, input().split()))
	prices = list(map(int, input().split()))
	baskets = {}
	for i in range(len(fruits)):
		if fruits[i] in baskets:
			baskets[fruits[i]] += prices[i]
		else:
			baskets[fruits[i]] = prices[i]
	print(sorted(baskets.values())[0])


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	F = list(map(int, input().split()))
	P = list(map(int, input().split()))
	Map = {}
	for k in range(N):
		Map[F[k]] = 0
	for j in range(N):
		Map[F[j]] += P[j]
	print(min(list(Map.values())))


T = int(input())
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	fruits = list(map(int, input().split()))
	baskets = list(map(int, input().split()))
	fruit_basket = {}
	for i in range(n):
		if fruit_basket.get(fruits[i]):
			fruit_basket[fruits[i]] += baskets[i]
		else:
			fruit_basket[fruits[i]] = baskets[i]
	basket_prices = list(fruit_basket.values())
	basket_prices.sort()
	print(basket_prices[0])


for x in range(int(input())):
	(n, m) = map(int, input().split())
	fruit_type = list(map(int, input().split()))
	price = list(map(int, input().split()))
	dict_temp = {}
	for x in range(len(fruit_type)):
		if fruit_type[x] in dict_temp.keys():
			dict_temp[fruit_type[x]] += price[x]
		else:
			dict_temp[fruit_type[x]] = price[x]
	print(min(dict_temp.values()))


for i in range(int(input())):
	(n, m) = map(int, input().split(' '))
	f = list(map(int, input().split(' ')))
	s = list(map(int, input().split(' ')))
	x = dict()
	for j in range(0, n):
		if f[j] not in x:
			x[f[j]] = s[j]
		else:
			x[f[j]] += s[j]
	res = []
	for j in x:
		res.append(x.get(j))
	print(min(res))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = [0] * (m + 1)
	for (i, p) in zip(map(int, input().split()), map(int, input().split())):
		c[i] += max(p, 0.01)
	print(int(min(filter(bool, c))))


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	fru_li = list(map(int, input().split()))
	pri_li = list(map(int, input().split()))
	di = {}
	for (i, j) in enumerate(fru_li):
		if j not in di:
			di[j] = pri_li[i]
		else:
			di[j] += pri_li[i]
	print(min(di.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if f[i] in d:
			d[f[i]] += p[i]
		else:
			d[f[i]] = p[i]
	maxi = 10 ** 13
	for (key, value) in d.items():
		maxi = min(maxi, value)
	print(maxi)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	ls = []
	x = set(f)
	for item in x:
		count = 0
		for i in range(n):
			if item == f[i]:
				count += p[i]
		ls.append(count)
	print(min(ls))


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	k = list(map(int, input().split()))
	z = []
	y = set(l)
	for g in y:
		sum = 0
		for j in range(n):
			if l[j] == g:
				sum += k[j]
		z.append(sum)
	z.sort()
	print(z[0])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ln = list(map(int, input().split()))
	pn = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if ln[i] in d.keys():
			d[ln[i]] = d[ln[i]] + pn[i]
		else:
			d[ln[i]] = pn[i]
	print(min(d.values()))


T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split()]
	F = [int(x) for x in input().split()]
	P = [int(x) for x in input().split()]
	c = []
	f = list(set(F))
	for j in f:
		s = 0
		for k in range(N):
			if F[k] == j:
				s = s + P[k]
		c.append(s)
	print(min(c))


testcases = int(input())
for i in range(testcases):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	temp = []
	temp1 = []
	for i in f:
		if i not in temp:
			temp.append(i)
	for i in temp:
		count = 0
		j = 0
		while j < len(f):
			if f[j] == i:
				count = count + p[j]
			j = j + 1
		temp1.append(count)
	print(min(temp1))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))[:n]
	p = list(map(int, input().split()))[:n]
	d = []
	for i in f:
		c = 0
		for j in range(n):
			if f[j] == i:
				c += p[j]
		d.append(c)
	print(min(d))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = list(map(int, input().split()))
	l = []
	prices = []
	for e in arr:
		if e not in l:
			l.append(e)
	for item in l:
		c = 0
		ind = arr.index(item)
		c += arr1[ind]
		for j in range(ind + 1, a):
			if arr[j] == item:
				c += arr1[j]
		prices.append(c)
	print(min(prices))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	price = {}
	for i in range(n):
		if f[i] not in price:
			price[f[i]] = p[i]
		else:
			price[f[i]] += p[i]
	min = price[f[0]]
	for i in price:
		if price[i] < min:
			min = price[i]
	print(min)


for x in range(int(input())):
	(n, k) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	b = [int(d) for d in input().split()]
	final = []
	s = list(set(a))
	for char in s:
		summ = 0
		for i in range(n):
			if a[i] == char:
				summ += b[i]
		final.append(summ)
	print(min(final))


t = int(input())
for tc in range(t):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	e = dict()
	for i in range(a):
		if c[i] in e:
			e[c[i]] += d[i]
		else:
			e[c[i]] = d[i]
	f = list(e.values())
	print(min(f))


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	n = {}
	for j in range(a):
		if x[j] not in n:
			n[x[j]] = y[j]
		else:
			n[x[j]] += y[j]
	print(min(n.values()))


from collections import defaultdict
t = int(input())
while t > 0:
	t -= 1
	li = list(map(int, input().split()))
	(N, M) = (li[0], li[1])
	fruits = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(len(fruits)):
		d[fruits[i]].append(cost[i])
	min1 = 100000
	for i in dict(d):
		if sum(d.get(i)) < min1:
			min1 = sum(d.get(i))
	print(min1)


t = input()
for c in range(0, int(t)):
	(n, m) = map(int, input().split())
	f = list(map(int, input().split()))
	p = list(map(int, input().split()))
	s = []
	for i in range(len(f)):
		c = 0
		t = 0
		for j in range(len(f)):
			if f[i] == f[j]:
				c += 1
				t += p[j]
		s.append(t)
	print(min(s))