In the world of DragonBool there are fierce warriors called Soints. Also there are even fiercer warriors called Sofloats – the mortal enemies of Soints.

The power of each warrior is determined by the amount of chakra he possesses which is some positive integer. Warriors with zero level of chakra are dead warriors :) When the fight between Soint with power C_{I} and Sofloat with power C_{F} occurs the warrior with lower power will die and the winner will lose the amount of chakra that his enemy have possessed before the fight. So three cases are possible:
C_{I} > C_{F}. Then Sofloat will die while the new power of Soint will be C_{I} – C_{F}.

C_{I} < C_{F}. Then Soint will die while the new power of Sofloat will be C_{F} – C_{I}.

C_{I} = C_{F}. In this special case both warriors die.

Each warrior (Soint or Sofloat) has his level of skills which is denoted by some positive integer. The fight between two warriors can occur only when these warriors are Soint and Sofloat of the same level. In particual, friendly fights are not allowed, i.e., a Soint cannot fight with another Soint and the same holds for Sofloats.

Lets follow the following convention to denote the warriors. A Soint of level L and power C will be denoted as (I, C, L), while Sofloat of level L and power C will be denoted as (F, C, L). Consider some examples. If A = (I, 50, 1) fights with B = (F, 20, 1), B dies and A becomes (I, 30, 1). On the other hand, (I, 50, 1) cannot fight with (F, 20, 2) as they have different levels.

There is a battle between Soints and Sofloats. There are N Soints and M Sofloats in all. The battle will consist of series of fights. As was mentioned above in each fight one Soint and one Sofloat of the same level take part and after the fight the warrior with lower power will die (or both will die if they have the same power). The battle proceeds as long as there exists at least one pair of warriors who can fight. The distribution of warriors by levels satisfies the following condition: for every Soint of level L there exists at least one Sofloat of the same level L and vice-versa. So if for some level L we have at least one warrior of this level then there is at least one Soint of level L and at least one Sofloat of level L.

There is a powerful wizard, whose name is SoChef, on the side of Soints. He can increase the amount of chakra of each Soint by any number. SoChef wants the army of Soints to win this battle. But increasing amount of chakra of any Soint by one costs him a lot of his magic power. Hence he wants to minimize the total amount of additional chakra he should give to Soints in order for them to win. Note, however, that the win here means that all Sofloats should be dead irregardless of whether any Soint is alive. Also note that the battle can proceed by different scenarios and the SoChef need to distribute additional chakra among the Soints in such a way that they will win for any possible battle scenario. Help SoChef and find the minimal amount of additional chakra he should give to Soints in order for them to win.

------ Input ------ 

The first line of the input contains an integer T, the number of test cases. T test cases follow. The first line of each test case contains two space separated integers N and M. Here N is the number of Soints  participating in the battle and M is the number of Sofloats  for the same. Each of the next N lines contains two space separated integers  C_{i} and  L_{i}, the amount of chakra and level of i-th Soint correspondingly. The next M lines describe power and level of Sofloats participating in the battle in the same format.

------ Output ------ 

For each test case output a single integer on a single line, the minimum amount of chakra SoChef should give to Soints in order for them to win the battle.

------ Constraints ------ 

Each integer in the input file is positive and does not exceed 100. That is
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ M ≤ 100
1 ≤ C_{i} ≤ 100
1 ≤ L_{i} ≤ 100
For every Soint of level L there exists at least one Sofloat of the same level L and vice-versa.
It is guaranteed that each official test file will satisfy all these constraints. You DON'T need to verify them in your program.

----- Sample Input 1 ------ 
2
2 3
10 1
20 2
5 2
5 2
18 1
5 5
73 87
69 13
36 36
77 46
43 93
49 46
74 93
78 87
99 13
59 36
----- Sample Output 1 ------ 
8
89
----- explanation 1 ------ 

Case 1.
The warriors are I1 = (I, 10, 1), I2 = (I, 20, 2), F1 = (F, 5, 2), F2 = (F, 5, 2), F3 = (F, 18, 1). Without the SoChef help the battle can proceed as follows.

I2 fights with F1, F1 dies, I2 becomes (I, 15, 2).
I2 fights with F2, F2 dies, I2 becomes (I, 10, 2).
I1 fights with F3, I1 dies, F3 becomes (F, 8, 1).

So if SoChef will give 8 additional units of chakra to I1 the Soints will win the battle and even one Soint (I2) will left alive. Hence the answer is 8.

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
t = int(input())
while t:
	(n, m) = map(int, input().split())
	si = {}
	sf = {}
	a = []
	for i in range(n):
		(c, l) = map(int, input().split())
		if l not in a:
			a.append(l)
		if l in si:
			si[l] += c
		else:
			si[l] = c
	for i in range(m):
		(c, l) = map(int, input().split())
		if l in sf:
			sf[l] += c
		else:
			sf[l] = c
	x = 0
	for i in a:
		if si[i] < sf[i]:
			x += sf[i] - si[i]
	print(x)
	t -= 1


for _ in range(int(input())):
	net = [0] * 101
	levs = set()
	z = input().split()
	(n, m) = map(int, z[:2])
	for _ in range(n):
		z = input().split()
		(ch, lv) = map(int, z[:2])
		levs |= {lv}
		net[lv] += ch
	for _ in range(m):
		z = input().split()
		(ch, lv) = map(int, z[:2])
		net[lv] -= ch
	boost = 0
	for lv in levs:
		if net[lv] < 0:
			boost -= net[lv]
	print(boost)


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	d = dict()
	for j in range(n):
		(ci, li) = map(int, input().split())
		if li in d:
			d[li] += -ci
		else:
			d[li] = -ci
	for k in range(m):
		(cf, lf) = map(int, input().split())
		d[lf] += cf
	x = 0
	for j in d:
		if d[j] > 0:
			x += d[j]
	print(x)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	(soints, sofloats) = ({}, {})
	for i in range(n):
		(c, l) = [int(k) for k in input().split()]
		soints[l] = soints.get(l, 0) + c
	for i in range(m):
		(c, l) = [int(k) for k in input().split()]
		sofloats[l] = sofloats.get(l, 0) + c
	chakra = 0
	for i in soints:
		if soints[i] < sofloats[i]:
			chakra = chakra + sofloats[i] - soints[i]
	print(chakra)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	a = [0 for j in range(101)]
	for i in range(n):
		(b, c) = map(int, input().split())
		a[c] += b
	for i in range(m):
		(k, l) = map(int, input().split())
		a[l] -= k
	sum = 0
	for x in range(101):
		if a[x] < 0:
			sum += a[x]
	print(abs(sum))


class Solution(object):

	def __init__(self):
		self.t = int(input())
		self.num_ints = 0
		self.num_floats = 0
		self.int_power = []
		self.int_level = []
		self.float_power = []
		self.float_level = []
		for _ in range(self.t):
			self.get_data()
			self.solve()
			self.clear_data()
	pass

	def get_data(self):
		(self.num_ints, self.num_floats) = map(int, input().split())
		Solution.fill_data(self.num_ints, self.int_power, self.int_level)
		Solution.fill_data(self.num_floats, self.float_power, self.float_level)
		pass

	@classmethod
	def fill_data(cls, num_ints, int_power, int_level):
		for _ in range(num_ints):
			(x, y) = map(int, input().split())
			int_power.append(x)
			int_level.append(y)
		pass

	def clear_data(self):
		self.int_level.clear()
		self.int_power.clear()
		self.float_level.clear()
		self.float_power.clear()
		pass

	def solve(self):
		int_level_to_power = Solution.get_level_to_power(self.int_level, self.int_power)
		float_level_to_power = Solution.get_level_to_power(self.float_level, self.float_power)
		for (x, y) in int_level_to_power.items():
			pf = float_level_to_power[x]
			if pf <= y:
				del float_level_to_power[x]
			else:
				float_level_to_power[x] -= y
		print(sum(float_level_to_power.values()))
		pass

	@classmethod
	def get_level_to_power(cls, int_level, int_power):
		out = dict()
		for i in range(len(int_level)):
			if int_level[i] in out:
				out[int_level[i]] += int_power[i]
			else:
				out[int_level[i]] = int_power[i]
		return out
		pass

def main():
	Solution()
	pass
main()


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	soldiers = dict()
	for __ in range(N):
		(c, l) = map(int, input().split())
		if l in soldiers:
			soldiers[l] += -c
		else:
			soldiers[l] = -c
	for __ in range(M):
		(c, l) = map(int, input().split())
		soldiers[l] += c
	magic = 0
	for level in soldiers:
		if soldiers[level] > 0:
			magic += soldiers[level]
	print(magic)


t = int(input())
for i in range(0, t):
	(n, m) = input().strip().split()
	n = int(n)
	m = int(m)
	a = [0] * 101
	b = [0] * 101
	for j in range(0, n):
		(s, d) = input().strip().split()
		s = int(s)
		d = int(d)
		a[d] += s
	for k in range(0, m):
		(g, h) = input().strip().split()
		g = int(g)
		h = int(h)
		b[h] += g
	add = 0
	for v in range(0, 101):
		if b[v] > a[v]:
			add += b[v] - a[v]
	print(add)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	Si = []
	Sf = []
	cntd = []
	for _ in range(N):
		[C, L] = list(input().split())
		Si += [[C, L]]
	for _ in range(M):
		[C, L] = list(input().split())
		Sf += [[C, L]]
	t = 0
	ans = 0
	for x in Si:
		if len(cntd) >= 1:
			for a in cntd:
				if a == x[1]:
					t = 1
					break
		if t == 1:
			t = 0
			continue
		totSi = 0
		cntd += [x[1]]
		for a in Si:
			if a[1] == x[1]:
				totSi += int(a[0])
		totSf = 0
		for b in Sf:
			if b[1] == x[1]:
				totSf += int(b[0])
		if totSi >= totSf:
			continue
		else:
			ans += totSf - totSi
			continue
	print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(d1, d2) = ({}, {})
	for i in range(a + b):
		(d, c) = map(int, input().split())
		if i < a:
			if c not in d1:
				d1[c] = d
			else:
				d1[c] += d
		elif c not in d2:
			d2[c] = d
		else:
			d2[c] += d
	for i in d2:
		if i in d1:
			if d2[i] > d1[i]:
				d2[i] = d2[i] - d1[i]
			else:
				d2[i] = 0
	print(sum(d2.values()))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = [0] * 101
	for i in range(n):
		(c, l) = map(int, input().split())
		d[l] += c
	for i in range(m):
		(c, l) = map(int, input().split())
		d[l] -= c
	ans = 0
	for i in range(101):
		if d[i] < 0:
			ans -= d[i]
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	soint = []
	for i in range(N):
		(p, l) = map(int, input().split())
		soint.append([p, l])
	sofloat = []
	for i in range(M):
		(p, l) = map(int, input().split())
		sofloat.append([p, l])
	chakra = 0
	for i in sofloat:
		power_sofloat = i[0]
		level_sofloat = i[1]
		for j in soint:
			power_soint = j[0]
			level_soint = j[1]
			if j[1] == i[1]:
				if j[0] < i[0]:
					i[0] -= j[0]
					j[0] = 0
				elif i[0] < j[0]:
					j[0] -= i[0]
					i[0] = 0
				else:
					i[0] = 0
					j[0] = 0
	for i in sofloat:
		chakra += i[0]
	print(chakra)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	soi = {}
	sof = {}
	for __ in range(n):
		(c, l) = map(int, input().split())
		if l in soi.keys():
			soi[l] += c
		else:
			soi[l] = c
	for __ in range(m):
		(c, l) = map(int, input().split())
		if l in sof.keys():
			sof[l] += c
		else:
			sof[l] = c
	chakra = 0
	for key in soi.keys():
		if soi[key] < sof[key]:
			chakra += sof[key] - soi[key]
	print(chakra)


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	soints_dict = {}
	for j in range(n):
		(c, l) = map(int, input().split())
		if l in soints_dict:
			soints_dict[l] += c
		else:
			soints_dict[l] = c
	ans = 0
	for j in range(m):
		(c, l) = map(int, input().split())
		temp = soints_dict[l] - c
		if temp < 0:
			soints_dict[l] = 0
			ans += abs(temp)
		else:
			soints_dict[l] -= c
	print(ans)


from collections import defaultdict as dt
t = input()
for cc in range(0, int(t)):
	(n, m) = map(int, input().split())
	soints = dt(list)
	for i in range(n):
		(k, p) = map(int, input().split())
		soints[p].append(k)
	sofl = dt(list)
	for i in range(m):
		(k, p) = map(int, input().split())
		sofl[p].append(k)
	so = dt(int)
	for i in soints.keys():
		for j in soints[i]:
			so[i] += j
	sof = dt(int)
	for i in sofl.keys():
		for j in sofl[i]:
			sof[i] += j
	count = 0
	for i in so:
		if so[i] < sof[i]:
			count += sof[i] - so[i]
	print(count)


from collections import Counter
for t in range(int(input())):
	w = Counter()
	z = Counter()
	(n, m) = map(int, input().split())
	x = []
	y = []
	for i in range(n):
		(c, l) = map(int, input().split())
		x.append((str(l), c))
	for i in range(m):
		(c, l) = map(int, input().split())
		y.append((str(l), c))
	for (l, c) in x:
		w[l] += c
	for (l, c) in y:
		z[l] += c
	x = sorted(list(w.items()))
	y = sorted(list(z.items()))
	k = []
	for i in x:
		for j in y:
			if i[1] - j[1] < 0:
				k.append(i[1] - j[1])
			y.pop(0)
			break
	print(sum(k) * -1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	dicn = {}
	dicm = {}
	for j in range(n):
		(c, l) = map(int, input().split())
		if l in dicn.keys():
			dicn[l] += c
		else:
			dicn[l] = c
	for j in range(m):
		(c, l) = map(int, input().split())
		if l in dicm.keys():
			dicm[l] += c
		else:
			dicm[l] = c
	sum = 0
	for j in dicn.keys():
		if dicn[j] >= dicm[j]:
			continue
		else:
			sum += abs(dicn[j] - dicm[j])
	print(sum)


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	soi = {}
	sof = {}
	for j in range(0, n):
		(c, l) = map(int, input().split())
		if not l in soi.keys():
			soi[l] = c
		else:
			soi[l] += c
	for j in range(0, m):
		(c, l) = map(int, input().split())
		if not l in sof.keys():
			sof[l] = c
		else:
			sof[l] += c
	sum = 0
	for i in soi.keys():
		if soi[i] < sof[i]:
			sum += sof[i] - soi[i]
	print(sum)


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	(so, sof) = ([], [])
	(ip, fp) = (0, 0)
	for i in range(n):
		(c, l) = map(int, input().split())
		so.append(['i', c, l])
	for i in range(m):
		(c, l) = map(int, input().split())
		so.append(['f', c, l])
	levels = set([l for (a, c, l) in so])
	chakra = []
	for level in levels:
		a = [(a, c) for (a, c, l) in so if l == level]
		(ip, fp) = (0, 0)
		for i in a:
			if i[0] == 'i':
				ip += i[1]
			else:
				fp += i[1]
		if ip - fp < 0:
			chakra.append(abs(ip - fp))
	print(sum(chakra))


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().strip().split()))
	d = dict()
	for j in range(n):
		(a, b) = list(map(int, input().strip().split()))
		if b in d:
			d[b] += a
		else:
			d[b] = a
	for k in range(m):
		(a, b) = list(map(int, input().strip().split()))
		d[b] -= a
	ans = 0
	for val in d:
		if d[val] < 0:
			ans += -1 * d[val]
	print(ans)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	m = temp[1]
	lsoi = []
	lsof = []
	csoi = []
	csof = []
	for i in range(101):
		lsoi.append(0)
		csoi.append(0)
		lsof.append(0)
		csof.append(0)
	for i in range(n):
		temp = list(map(int, input().split()))
		csoi[temp[1]] += 1
		lsoi[temp[1]] += temp[0]
	for i in range(m):
		temp = list(map(int, input().split()))
		csof[temp[1]] += 1
		lsof[temp[1]] += temp[0]
	ans = 0
	for i in range(1, 101):
		if lsoi[i] == lsof[i]:
			csoi[i] = 0
		elif lsoi[i] < lsof[i]:
			csoi[i] = 0
			ans += lsof[i] - lsoi[i]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * 101
	for i in range(n):
		(a, b) = map(int, input().split())
		l[b] += a
	for j in range(m):
		(a, b) = map(int, input().split())
		l[b] -= a
	s = 0
	for i in l:
		if i < 0:
			s += i
	print(s * -1)


test = int(input())
for case in range(test):
	(n_i, n_f) = [int(val) for val in input().split(' ')]
	I = {}
	F = {}
	for k in range(n_i):
		wrior = [int(val) for val in input().split(' ')]
		if wrior[1] in I.keys():
			I[wrior[1]] += wrior[0]
		else:
			I[wrior[1]] = wrior[0]
	for k in range(n_f):
		wrior = [int(val) for val in input().split(' ')]
		if wrior[1] in F.keys():
			F[wrior[1]] += wrior[0]
		else:
			F[wrior[1]] = wrior[0]
	cmn = []
	for val in I.keys():
		if val in F.keys():
			cmn.append(val)
	chk = 0
	for val in cmn:
		if I[val] < F[val]:
			chk += F[val] - I[val]
	print(chk)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	dic = dict()
	for _ in range(n):
		(a, b) = list(map(int, input().strip().split()))
		if b in dic:
			dic[b] += a
		else:
			dic[b] = a
	for _ in range(m):
		(a, b) = list(map(int, input().strip().split()))
		dic[b] -= a
	req = 0
	for value in dic:
		if dic[value] < 0:
			req += -1 * dic[value]
	print(req)


t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	c1 = [0] * 105
	c2 = [0] * 105
	h = 0
	for i in range(n):
		(c, l) = map(int, input().split())
		c1[l] += c
	for i in range(m):
		(c, l) = map(int, input().split())
		c2[l] += c
	for i in range(0, 101):
		if c2[i] > c1[i]:
			h += c2[i] - c1[i]
	print(h)
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = {}
	for j in range(n):
		(v, k) = map(int, input().split())
		try:
			a[k] += v
		except:
			a[k] = v
	for j in range(m):
		(v, k) = map(int, input().split())
		a[k] -= v
	p = 0
	for j in a.keys():
		if a[j] < 0:
			p += abs(a[j])
	print(p)


T = int(input())
while T:
	LI = [0 for _ in range(100)]
	LF = [0 for _ in range(100)]
	SC = 0
	(N, M) = map(int, input().split())
	for i in range(N):
		(c, l) = map(int, input().split())
		LI[l - 1] += c
	for i in range(M):
		(c, l) = map(int, input().split())
		LF[l - 1] += c
	for i in range(100):
		if LI[i] < LF[i]:
			SC += LF[i] - LI[i]
	print(SC)
	T -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	sointGang = {}
	soflatGang = {}
	chakra = 0
	for i in range(n):
		(C, L) = map(int, input().split())
		if L not in sointGang.keys():
			sointGang[L] = C
		else:
			sointGang[L] += C
	for i in range(m):
		(C, L) = map(int, input().split())
		if L not in soflatGang.keys():
			soflatGang[L] = C
		else:
			soflatGang[L] += C
	for level in soflatGang.keys():
		if soflatGang[level] > sointGang[level]:
			chakra += abs(soflatGang[level] - sointGang[level])
	print(chakra)


t = int(input())
for _ in range(t):
	(n, m) = (int(x) for x in input().split())
	a = []
	b = []
	for _ in range(101):
		a.append([])
		b.append([])
	for _ in range(n):
		(c, l) = (int(x) for x in input().split())
		a[l].append(c)
	for _ in range(m):
		(c, l) = (int(x) for x in input().split())
		b[l].append(c)
	count = 0
	for i in range(1, 101):
		tmp_a = sum(a[i])
		tmp_b = sum(b[i])
		if tmp_b > tmp_a:
			count += tmp_b - tmp_a
	print(count)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	soints = {}
	sofloats = {}
	while n:
		(c, l) = map(int, input().split())
		if l in soints.keys():
			soints[l] += c
		else:
			soints[l] = c
		n -= 1
	while m:
		(c, l) = map(int, input().split())
		if l in sofloats.keys():
			sofloats[l] += c
		else:
			sofloats[l] = c
		m -= 1
	c = 0
	for l in soints.keys():
		if sofloats[l] >= soints[l]:
			c += sofloats[l] - soints[l]
	print(c)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = dict()
	for _ in range(n):
		(c, l) = map(int, input().split())
		if l in s:
			s[l] += -c
		else:
			s[l] = -c
	for _ in range(m):
		(c, l) = map(int, input().split())
		s[l] += c
	m = 0
	for i in s:
		if s[i] > 0:
			m += s[i]
	print(m)


from collections import defaultdict
a = int(input())
for _ in range(a):
	table1 = defaultdict(int)
	table2 = defaultdict(int)
	b = list(map(int, input().split()))
	for i in range(b[0]):
		aa = list(map(int, input().split()))
		table1[aa[1]] += aa[0]
	for i in range(b[1]):
		ba = list(map(int, input().split()))
		table2[ba[1]] += ba[0]
	count = 0
	for i in table1:
		if table1[i] >= table2[i]:
			pass
		else:
			count += table2[i] - table1[i]
	print(count)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	d1 = {}
	d = {}
	for i in range(n):
		(a, b) = map(int, input().split())
		if b not in d1.keys():
			d1[b] = a
		else:
			x = d1[b]
			d1[b] = x + a
	for i in range(m):
		(a, b) = map(int, input().split())
		if b not in d.keys():
			d[b] = a
		else:
			x = d[b]
			d[b] = x + a
	c = 0
	count = 0
	for i in d:
		if d1[i] > d[i]:
			c = 1
		elif d1[i] < d[i]:
			count += d[i] - d1[i]
		else:
			continue
	print(count)


from sys import stdin
from operator import add
from functools import reduce
T = int(stdin.readline().strip())
while T > 0:
	[N, M] = [int(n) for n in stdin.readline().strip().split()]
	dict1 = {}
	for i in range(0, N):
		[C, L] = [int(n) for n in stdin.readline().strip().split()]
		if L not in dict1:
			dict1[L] = C
		else:
			dict1[L] += C
	for i in range(0, M):
		[C, L] = [int(n) for n in stdin.readline().strip().split()]
		dict1[L] -= C
	print(-reduce(add, [n for n in dict1.values() if n < 0], 0))
	T -= 1


t = int(input())
for t0 in range(t):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	a = dict()
	b = dict()
	st = set()
	for n0 in range(n):
		(v, k) = [int(i) for i in input().strip().split(' ')]
		if k in a:
			a[k] += v
		else:
			a[k] = v
	for m0 in range(m):
		(v, k) = [int(i) for i in input().strip().split(' ')]
		if k in b:
			b[k] += v
		else:
			b[k] = v
	ct = 0
	for i in a:
		x = a[i]
		y = b[i]
		if x >= y:
			continue
		else:
			z = y - x
			ct += z
	print(ct)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	power_l = [[0, 0] for _ in range(101)]
	check_add = 0
	add = 0
	fight_level = []
	for _ in range(n):
		(c, l) = map(int, input().split())
		power_l[l][0] += c
		if l not in fight_level:
			fight_level.append(l)
	for _ in range(m):
		(c, l) = map(int, input().split())
		power_l[l][1] += c
	for f in fight_level:
		v = power_l[f]
		if v[1] > v[0]:
			add += v[1] - v[0]
	print(add)


t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	ints = [0] * 101
	for i in range(n):
		temp = list(map(int, input().split()))
		ints[temp[1]] += temp[0]
	floats = [0] * 101
	for i in range(m):
		temp = list(map(int, input().split()))
		floats[temp[1]] += temp[0]
	ans = 0
	for i in range(101):
		ans += max(0, floats[i] - ints[i])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	si = [0] * 101
	sf = [0] * 101
	for i in range(n):
		(c, l) = map(int, input().split())
		si[l] = si[l] + c
	for i in range(m):
		(c, l) = map(int, input().split())
		sf[l] = sf[l] + c
	cnt = 0
	win = False
	for i in range(1, 101):
		if si[i] > sf[i]:
			win = True
		elif si[i] == sf[i]:
			continue
		elif si[i] < sf[i]:
			cnt = cnt + sf[i] - si[i]
	print(cnt)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = [0] * 101
	for i in range(n):
		(a, b) = map(int, input().split())
		l[b] += a
	for j in range(m):
		(a, b) = map(int, input().split())
		l[b] -= a
	ans = 0
	for i in l:
		if i < 0:
			ans += abs(i)
	print(ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	warriors = {}
	for i in range(n):
		(c, l) = map(int, input().split())
		if l in warriors.keys():
			warriors[l] += c
		else:
			warriors[l] = c
	for i in range(m):
		(c, l) = map(int, input().split())
		warriors[l] -= c
	magic = 0
	for v in warriors.values():
		if v < 0:
			magic -= v
	print(magic)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	soint = [0] * 101
	sofloat = [0] * 101
	count = 0
	for i in range(n):
		(c, l) = map(int, input().split())
		soint[l] += c
	for i in range(m):
		(c, l) = map(int, input().split())
		sofloat[l] += c
	for i in range(1, 101):
		if sofloat[i] > soint[i]:
			count += sofloat[i] - soint[i]
	print(count)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	(s, t) = ({}, {})
	for j in range(n):
		(c, l) = map(int, input().split())
		if l in s.keys():
			s[l] += c
		else:
			s[l] = c
	for j in range(m):
		(c, l) = map(int, input().split())
		if l in t.keys():
			t[l] += c
		else:
			t[l] = c
	d = 0
	for key in s.keys():
		if s[key] < t[key]:
			d += t[key] - s[key]
	print(d)


for _ in range(int(input())):
	so = []
	si = []
	for i in range(100):
		so.append([])
		si.append([])
	ma = -1
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	while n:
		(p, l) = input().split()
		p = int(p)
		l = int(l)
		if l - 1 > ma:
			ma = l - 1
		si[l - 1].append(p)
		n -= 1
	while m:
		(p, l) = input().split()
		p = int(p)
		l = int(l)
		so[l - 1].append(p)
		m -= 1
	c = 0
	for i in range(ma + 1):
		if sum(so[i]) > sum(si[i]):
			c += sum(so[i]) - sum(si[i])
	print(c)


def drgnbool():
	t = int(input())
	while t:
		(n, m) = map(int, input().split())
		soints = {}
		sofloats = {}
		while n:
			(ch, level) = map(int, input().split())
			if level in soints.keys():
				soints.get(level).append(ch)
			else:
				soints[level] = [ch]
			n -= 1
		while m:
			(ch, level) = map(int, input().split())
			if level in sofloats.keys():
				sofloats.get(level).append(ch)
			else:
				sofloats[level] = [ch]
			m -= 1
		reinforcement = 0
		for key in soints.keys():
			sum1 = sum(soints.get(key))
			sum2 = sum(sofloats.get(key))
			if sum2 > sum1:
				reinforcement += sum2 - sum1
		print(reinforcement)
		t -= 1
drgnbool()


t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	dn = dict()
	dm = dict()
	for nj in range(n):
		(j, i) = map(int, input().split())
		if i not in dn.keys():
			dn[i] = j
		else:
			dn[i] += j
	for mj in range(m):
		(j, i) = map(int, input().split())
		if i not in dm.keys():
			dm[i] = j
		else:
			dm[i] += j
	count = 0
	for i in dn.keys():
		if dn[i] < dm[i]:
			count = count + dm[i] - dn[i]
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [0 for i in range(101)]
	for k in range(n):
		(c, l) = map(int, input().split())
		a[l] += c
	for k in range(m):
		(c, l) = map(int, input().split())
		a[l] -= c
	ans = 0
	for i in range(101):
		if a[i] < 0:
			ans += abs(a[i])
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	(soint, sofloat) = ({}, {})
	for _ in range(n):
		(c, l) = [int(x) for x in input().split()]
		if soint.get(l):
			soint[l] += c
		else:
			soint[l] = c
	for _ in range(m):
		(c, l) = [int(x) for x in input().split()]
		if sofloat.get(l):
			sofloat[l] += c
		else:
			sofloat[l] = c
	ans = 0
	for i in soint:
		sofloat[i] -= soint[i]
		if sofloat[i] > 0:
			ans += sofloat[i]
	print(ans)


for j in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = ({}, {})
	for i in range(n):
		(a, b) = map(int, input().split())
		if b in x:
			x[b] += a
		else:
			x[b] = a
	for i in range(m):
		(c, d) = map(int, input().split())
		if d in y:
			y[d] += c
		else:
			y[d] = c
	z = []
	for i in x:
		a = x[i] - y[i]
		if a <= 0:
			z.append(a)
	print(abs(sum(z)))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ci = {}
	cm = {}
	for i in range(n):
		(c, l) = map(int, input().split())
		if l not in ci.keys():
			ci[l] = c
		else:
			ci[l] += c
	for i in range(m):
		(c, l) = map(int, input().split())
		if l not in cm.keys():
			cm[l] = c
		else:
			cm[l] += c
	count = 0
	for i in ci.keys():
		if ci[i] < cm[i]:
			count += cm[i] - ci[i]
	print(count)


from collections import defaultdict
for _ in range(int(input())):
	dic1 = defaultdict(list)
	dic2 = defaultdict(list)
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
		dic1[a[i][1]].append(a[i][0])
	b = []
	for i in range(m):
		b.append(list(map(int, input().split())))
		dic2[b[i][1]].append(b[i][0])
	su = 0
	for i in dic1.keys():
		s1 = sum(dic1[i])
		s2 = sum(dic2[i])
		if s2 > s1:
			su += s2 - s1
	print(su)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	add = [0] * 101
	for i in range(n):
		(takat, index) = map(int, input().split())
		add[index] = add[index] + takat
	for i in range(m):
		(takat, index) = map(int, input().split())
		add[index] = add[index] - takat
	sum1 = 0
	for i in add:
		if i < 0:
			sum1 = sum1 + abs(i)
	print(sum1)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	s_i = {}
	for j in range(n):
		(c, l) = map(int, input().split())
		if l in s_i:
			s_i[l] = s_i[l] + c
		else:
			s_i[l] = c
	s_f = {}
	for j in range(m):
		(c, l) = map(int, input().split())
		if l in s_f:
			s_f[l] = s_f[l] + c
		else:
			s_f[l] = c
	need = 0
	for j in s_i:
		(ci, cf) = (s_i[j], s_f[j])
		if ci < cf:
			need += cf - ci
	print(need)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(dn, dm) = ({}, {})
	for t in range(n):
		(c, l) = map(int, input().split())
		dn[l] = dn.get(l, 0) + c
	for t in range(m):
		(c, l) = map(int, input().split())
		dm[l] = dm.get(l, 0) + c
	ans = 0
	for (x, y) in dn.items():
		ans += max([0, dm[x] - y])
	print(ans)


try:
	tst = int(input())
except:
	tst = 0
for j in range(tst):
	t = list(map(int, input().split()))
	war = {}
	for i in range(t[0]):
		soint = list(map(int, input().split()))
		if soint[1] in war.keys():
			war[soint[1]][0].append(soint[0])
		else:
			war[soint[1]] = [[], []]
			war[soint[1]][0].append(soint[0])
	for i in range(t[1]):
		sofloat = list(map(int, input().split()))
		war[sofloat[1]][1].append(sofloat[0])
	ans = 0
	for i in war.keys():
		a = sum(war[i][0])
		b = sum(war[i][1])
		if b > a:
			ans = ans + b - a
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	di = {}
	df = {}
	level = set()
	for j in range(n):
		(c, l) = map(int, input().split())
		level.add(l)
		if di.get(l) == None:
			di[l] = c
		else:
			di[l] = di[l] + c
	for j in range(m):
		(c, l) = map(int, input().split())
		if df.get(l) == None:
			df[l] = c
		else:
			df[l] = df[l] + c
	point = 0
	level = list(level)
	for j in range(len(level)):
		if di.get(level[j]) < df.get(level[j]):
			point += df[level[j]] - di[level[j]]
	print(point)


t = int(input())
while t > 0:
	nm = str(input())
	(n, m) = nm.split(' ')
	n = int(n)
	m = int(m)
	sn = []
	sm = []
	s = {}
	i = 0
	j = 0
	temp = []
	while i < n:
		sn.append([])
		sn[i] = str(input()).split(' ')
		sn[i] = [int(i) for i in sn[i]]
		try:
			s[sn[i][1]] = s[sn[i][1]] + sn[i][0]
		except:
			s[sn[i][1]] = sn[i][0]
		if not sn[i][1] in temp:
			temp.append(sn[i][1])
			j += 1
		i += 1
	i = 0
	while i < m:
		sm.append([])
		sm[i] = str(input()).split(' ')
		sm[i] = [int(i) for i in sm[i]]
		s[sm[i][1]] = s[sm[i][1]] - sm[i][0]
		i += 1
	ans = 0
	i = 0
	l = len(temp)
	while i < l:
		if s[temp[i]] < 0:
			ans = ans + s[temp[i]]
		i += 1
	print(abs(ans))
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(soint_arr, sofloat_arr) = ([], [])
	for i in range(n):
		temp = tuple(map(int, input().split()))
		soint_arr.append(temp)
	for i in range(m):
		temp = tuple(map(int, input().split()))
		sofloat_arr.append(temp)
	sofloat_arr.sort(key=lambda x: x[1])
	soint_arr.sort(key=lambda x: x[1])
	level = []
	for ele in soint_arr:
		if ele[1] not in level:
			level.append(ele[1])
	chakra = 0
	(i, j) = (0, 0)
	for ele in level:
		(count1, count2) = (0, 0)
		while i < len(soint_arr) and soint_arr[i][1] == ele:
			count1 += soint_arr[i][0]
			i += 1
		while j < len(sofloat_arr) and sofloat_arr[j][1] == ele:
			count2 += sofloat_arr[j][0]
			j += 1
		if count1 < count2:
			chakra += count2 - count1
	print(chakra)


try:
	t = int(input())
except:
	t = 0
for i in range(t):
	try:
		x = list(map(int, input().split()))
		soint = [0] * 101
		sofloat = [0] * 101
		for j in range(x[0]):
			try:
				y = list(map(int, input().split()))
			except:
				y = [0, 0]
			soint[y[1]] += y[0]
		for k in range(x[1]):
			try:
				z = list(map(int, input().split()))
			except:
				z = [0, 0]
			sofloat[z[1]] += z[0]
		ans = 0
		for l in range(101):
			if sofloat[l] > soint[l]:
				ans = ans + (sofloat[l] - soint[l])
		print(ans)
	except:
		pass


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	soInt = {}
	for n in range(N):
		(c, l) = map(int, input().split())
		if l in soInt:
			soInt[l] += c
		else:
			soInt[l] = c
	soFloat = {}
	for m in range(M):
		(c, l) = map(int, input().split())
		if l in soFloat:
			soFloat[l] += c
		else:
			soFloat[l] = c
	for i in soFloat:
		if i in soInt:
			if soFloat[i] > soInt[i]:
				soFloat[i] -= soInt[i]
			else:
				soFloat[i] = 0
	print(sum(soFloat.values()))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	INTS = {}
	FLOATS = {}
	for i in range(1, 101):
		INTS[i] = 0
		FLOATS[i] = 0
	for i in range(N):
		(C, L) = map(int, input().split())
		INTS[L] += C
	for i in range(M):
		(C, L) = map(int, input().split())
		FLOATS[L] += C
	ans = 0
	for i in range(1, 101):
		if FLOATS[i] > INTS[i]:
			ans += FLOATS[i] - INTS[i]
	print(ans)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	dick = {}
	dicky = {}
	for i in range(N):
		(C, L) = map(int, input().split())
		if L not in dick:
			dick[L] = C
		else:
			dick[L] += C
	for i in range(M):
		(c, l) = map(int, input().split())
		if l not in dicky:
			dicky[l] = c
		else:
			dicky[l] += c
	for ele in dicky:
		if ele in dick:
			if dicky[ele] > dick[ele]:
				dicky[ele] -= dick[ele]
			else:
				dicky[ele] = 0
	x = sum(dicky.values())
	print(x)