There are $n$ red balls kept on the positive $X$ axis, and $m$ blue balls kept on the positive $Y$ axis. You are given the positions of the balls. For each $i$ from $1$ to $n$, the $i$-th red ball has the coordinates $(x_i, 0)$, where $x_i$ is a positive integer. For each $i$ from $1$ to $m$, the $i$-th blue ball has the coordinates $(0, y_i)$, where $ y_i$ is a positive integer. 
It is given that all $x_i$ are distinct. Also, all $y_i$ are distinct.
At the time $t= 0$, for each $i$ from $1$ to $n$, the $i^{\text{th}}$ red ball is thrown towards positive $Y$ axis with a speed of $u_i$( that is, with velocity vector $(0, u_i)$). Simultaneously (at time $t = 0$), for each $i$ from $1$ to $m$, the $i^{\text{th}}$ blue ball is thrown towards positive $X$ axis with a speed of $v_i$ (that is, with velocity vector $(v_i, 0)$).
Two balls are said to collide if they are at the same position at the same time. When two balls collide, they disappear, and hence no longer collide with other balls. (See sample examples for clarification).
Find the total number of collisions the balls will have.

-----Input-----
- First line contains $n$ and $m$, the number of red balls, and the number of blue balls, respectively. 
- $i^{\text{th}}$  of the next $n$ lines contains two space separated integers $x_i$ and $u_i$, the position and speed of the $i^{\text{th}}$  red ball respectively
- $i^{\text{th}}$  of the next $m$ lines contains two space separated integers $y_i$ and $v_i$, the position and speed of the $i^{\text{th}}$  blue ball respectively

-----Output-----
Print the number of collisions.

-----Constraints-----
- $1 \le n, m \le 10^5$
- $1 \le x_i, u_i, y_i, v_i \le 10^9$
- for all $1 \le i < j \le n, x_i \neq x_j$
- for all $1 \le i < j \le m, y_i \neq y_j$

-----Example Input 1-----
1 1
1 2
2 1

-----Example Output 1-----
1

-----Example Input 2-----
1 2
1 2
2 1
1 2

-----Example Output 2-----
1

-----Explanation-----
Example case 1: The balls collide at t = 1, at the coordinates (1, 2). 
Example case 2: The red ball and the second blue ball collide at time 0.5 at coordinates (1, 1). Note that the first blue ball would have collided with the red ball at t = 1 (like in sample input # 1), if the second blue ball wasn't present. But since the red ball disappears at t = 0.5, its collision with first blue ball doesn't happen. The total number of collisions is 1.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
(n, m) = map(int, input().split())
red = []
for i in range(n):
	(a, b) = map(int, input().split())
	red.append(a * b)
d = {}
for i in range(m):
	(a, b) = map(int, input().split())
	p = a * b
	if p in d:
		d[p] += 1
	else:
		d[p] = 1
an = 0
for i in range(n):
	if red[i] in d and d[red[i]] > 0:
		an += 1
		d[red[i]] -= 1
print(an)


(n, m) = map(int, input().split())
l = []
c = dict()
for i in range(n):
	(x, u) = map(int, input().split())
	l.append(x * u)
for i in range(m):
	(y, v) = map(int, input().split())
	z = y * v
	if z in c:
		c[z] += 1
	else:
		c[z] = 1
co = 0
for i in range(n):
	if l[i] in c and c[l[i]] > 0:
		co += 1
		c[l[i]] -= 1
print(co)


t = 1
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	X = {}
	Y = {}
	for i in range(n):
		(x, u) = map(int, input().split())
		xu = x * u
		if xu in X:
			X[xu] = X[xu] + 1
		else:
			X[xu] = 1
	for i in range(m):
		(y, v) = map(int, input().split())
		yv = y * v
		if yv in Y:
			Y[yv] = Y[yv] + 1
		else:
			Y[yv] = 1
	ans = 0
	for i in X:
		if i in Y:
			m = min(X[i], Y[i])
			ans += m
	print(ans)


l = input().split()
n = int(l[0])
m = int(l[1])
l = []
for i in range(n):
	lo = input().split()
	l.append(int(lo[0]) * int(lo[1]))
hashi = dict()
for i in range(m):
	lo = input().split()
	z = int(lo[0]) * int(lo[1])
	if z in hashi:
		hashi[z] += 1
	else:
		hashi[z] = 1
count = 0
for i in range(n):
	if l[i] in hashi and hashi[l[i]] > 0:
		count += 1
		hashi[l[i]] -= 1
print(count)


import collections
(n, m) = map(int, input().split())
red = []
blue = []
for i in range(n):
	(x, u) = map(int, input().split())
	red.append(x * u)
for i in range(m):
	(y, v) = map(int, input().split())
	blue.append(y * v)
count = 0
r = dict(collections.Counter(red))
b = dict(collections.Counter(blue))
for i in r:
	if i in b:
		count += min(r[i], b[i])
print(count)


(n, m) = map(int, input().split())
(X, Y) = ({}, {})
for i in range(n):
	(x, u) = map(int, input().split())
	p = x * u
	if p in X:
		X[p] += 1
	else:
		X[p] = 1
for i in range(m):
	(y, v) = map(int, input().split())
	p = y * v
	if p in Y:
		Y[p] += 1
	else:
		Y[p] = 1
ans = 0
for i in X:
	if i in Y:
		ans += min(X[i], Y[i])
print(ans)


from collections import Counter
(n, m) = map(int, input().split())
(p1, p2) = ([], [])
for i in range(n):
	(x, u) = map(int, input().split())
	p1.append(x * u)
for i in range(m):
	(y, v) = map(int, input().split())
	p2.append(y * v)
d1 = dict(Counter(p1))
d2 = dict(Counter(p2))
s = 0
for x in d1:
	if x in d2:
		s += min(d1[x], d2[x])
print(s)


(n, m) = map(int, input().split())
x = dict()
for i in range(n):
	(a, b) = map(int, input().split())
	if a * b not in x:
		x[a * b] = 1
	else:
		x[a * b] += 1
cnt = 0
for i in range(m):
	(a, b) = map(int, input().split())
	if a * b in x and x[a * b] != 0:
		x[a * b] -= 1
		cnt += 1
print(cnt)


(n, m) = map(int, input().split())
x = {}
y = {}
for i in range(n):
	(p, s) = map(int, input().split())
	if p * s in x:
		x[p * s] += 1
	else:
		x[p * s] = 1
for i in range(m):
	(p, s) = map(int, input().split())
	if p * s in y:
		y[p * s] += 1
	else:
		y[p * s] = 1
c = 0
for i in x:
	if i in y:
		c += min(x[i], y[i])
print(c)


(n, m) = map(int, input().split())
(xco, yco) = ({}, {})
for i in range(n):
	(x, v) = map(int, input().split())
	try:
		xco[x * v] += 1
	except:
		xco[x * v] = 1
for i in range(m):
	(y, v) = map(int, input().split())
	try:
		yco[y * v] += 1
	except:
		yco[v * y] = 1
colli = 0
for i in xco:
	if i in yco:
		colli += min(xco[i], yco[i])
print(colli)


import functools
from bisect import bisect_left
arr = []
brr = []
(n, m) = list(map(int, input().split()))
for i in range(n):
	(x, u) = list(map(int, input().split()))
	arr.append((x * u, x))
arr.sort()
arr = [a[0] for a in arr]
for i in range(m):
	(y, v) = list(map(int, input().split()))
	brr.append((y, y * v))
brr.sort()
brr = [a[1] for a in brr]
count = 0
for i in range(m):
	pos = bisect_left(arr, brr[i])
	if pos < len(arr) and arr[pos] == brr[i]:
		count += 1
		arr.pop(pos)
print(count)


(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	l = list(map(int, input().split()))
	arr.append([l[0] * l[1], 0, l[0]])
for i in range(m):
	l = list(map(int, input().split()))
	arr.append([l[0] * l[1], 1, l[0]])
arr.sort()
i = 0
ans = 0
while i < m + n:
	if arr[i][1] == 1:
		i += 1
	else:
		w = i
		for j in range(i, m + n + 1):
			if j != m + n and arr[j][0] == arr[i][0]:
				if arr[j][1] == 1 and w == i:
					w = j
			else:
				break
		ans += min(w - i, j - w)
		i = j
print(ans)