You are a real estate broker in ancient Knossos. You have $m$ unsold houses, and each house $j$ has an area, $x_j$, and a minimum price, $y_j$. You also have $n$ clients, and each client $\boldsymbol{i}$ wants a house with an area greater than $a_i$ and a price less than or equal to $p_i$.

Each client can buy at most one house, and each house can have at most one owner. What is the maximum number of houses you can sell?

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the number of clients) and $m$ (the number of houses). 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains two space-separated integers describing the respective values of $a_i$ and $p_i$ for client $\boldsymbol{i}$. 

Each line $j$ of the $m$ subsequent lines contains two space-separated integers describing the respective values of $x_j$ and $y_j$ for house $j$.

Constraints

$1\leq n,m\leq1000$
$1\leq a_i,p_i\leq10^9$, where $0\leq i<n$.
$1\leq x_j,y_j\leq10^9$, where $0\leq j\lt m$.

Output Format

Print a single integer denoting the maximum number of houses you can sell.

Sample Input 0
3 3
5 110
9 500
20 400
10 100
2 200
30 300

Sample Output 0
2

Explanation 0

Recall that each client $\boldsymbol{i}$ is only interested in some house $j$ where $x_j>a_i$ and $y_j\leq p_i$. The diagram below depicts which clients will be interested in which houses:

Client $\mbox{o}$ will be interested in house $\mbox{o}$ because it has more than $a_{0}=5$ units of space and costs less than $p_{0}=110$. Both of the other houses are outside of this client's price range.
Client $\mbox{I}$ will be interested in houses $\mbox{o}$ and $2$, as both these houses have more than $a_1=9$ units of space and cost less than $p_1=500$. They will not be interested in the remaining house because it's too small.
Client $2$ will be interested in house $2$ because it has more than $a_{2}=20$ units of space and costs less than $p_2=400$. They will not be interested in the other two houses because they are too small.

All three clients are interested in the same two houses, so you can sell at most two houses in the following scenarios:   

Client $\mbox{o}$ buys house $\mbox{o}$ and client $\mbox{I}$ buys house $2$.
Client $\mbox{I}$ buys house $\mbox{o}$ and client $2$ buys house $2$.
Client $\mbox{o}$ buys house $\mbox{o}$ and client $2$ buys house $2$.

Thus, we print the maximum number of houses you can sell, $2$, on a new line.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
b = [tuple(map(int, input().split())) for _ in range(m)]
a.sort(reverse=True)
b.sort()
c = 0
for i in a:
	j = m - 1
	x = -1
	while j >= 0 and b[j][0] >= i[0]:
		if b[j][1] <= i[1] and (x < 0 or b[x][1] < b[j][1]):
			x = j
		j -= 1
	if x >= 0:
		c += 1
		b.pop(x)
		m -= 1
	if m == 0:
		break
print(c)


(n, m) = map(int, input().split())
clients = []
for i in range(n):
	clients.append(tuple(map(int, input().split())))
houses = []
for i in range(m):
	houses.append(tuple(map(int, input().split())))
cap = [[] for i in range(2 + n + m)]
for i in range(2, 2 + n):
	cap[0].append(i)
for i in range(2 + n, 2 + n + m):
	cap[i].append(1)
for ci in range(n):
	c = clients[ci]
	for hi in range(m):
		h = houses[hi]
		if h[0] > c[0] and h[1] <= c[1]:
			cap[2 + ci].append(2 + n + hi)
flow = [[] for i in range(2 + n + m)]
while True:
	visited = [False] * (2 + n + m)
	path = [0]
	while len(path) != 0:
		ci = path[-1]
		visited[ci] = True
		if ci == 1:
			for i in range(len(path) - 1):
				v1 = path[i]
				v2 = path[i + 1]
				cap[v1].remove(v2)
				if v1 in flow[v2]:
					flow[v2].remove(v1)
					cap[v2].append(v1)
				else:
					flow[v1].append(v2)
					cap[v2].append(v1)
			break
		else:
			for ni in cap[ci]:
				if not visited[ni]:
					path.append(ni)
					break
			if path[-1] == ci:
				path.pop()
	if len(path) == 0:
		break
print(len(flow[0]))


import copy
(clients, houses) = map(int, input().split())
client_con = [[]]
sinkx = clients + houses + 1
for _ in range(clients):
	(area, price) = map(int, input().split())
	client_con.append((area, price))
nodes = clients + houses + 2
clientxl = [_ for _ in range(1, clients + 1)]
housexl = [_ for _ in range(clients + 1, sinkx)]
blank_set = set([])
adjl = [set([]) for _ in range(nodes)]
adjl[0] = set(clientxl)
for house in housexl:
	adjl[house] = set([sinkx])
	(area, price) = map(int, input().split())
	for client in clientxl:
		if area > client_con[client][0] and price <= client_con[client][1]:
			adjl[client].add(house)

def bfs(source, sink):
	level = {_: 0 for _ in range(sink + 1)}
	que = [source]
	level_now = 1
	while que:
		next_que = []
		for node in que:
			for adj in adjl[node]:
				if level[adj] == 0 and adj != 0:
					next_que.append(adj)
					level[adj] = level_now
		level_now += 1
		que = copy.deepcopy(next_que)
	return level

def reset_his():
	for x in range(1, nodes):
		hisl[x] = False

def dfs(node, sink, flow=0):
	if node == sink:
		return flow + 1
	hisl[node] = True
	for adj in copy.copy(adjl[node]):
		if level[node] < level[adj] and (not hisl[adj]):
			if adjl[adj] != blank_set or adj == sink:
				d = dfs(adj, sink, flow)
				if d > flow:
					adjl[node].remove(adj)
					if node != 0:
						adjl[adj].add(node)
						return d
					else:
						flow = d
			else:
				adjl[node].remove(adj)
	return flow
total = 0
hisl = {_: False for _ in range(nodes)}
hisl_org = copy.copy(hisl)
while True:
	level = bfs(0, sinkx)
	if level[sinkx] == 0:
		break
	reset_his()
	new_flow = dfs(0, sinkx)
	total += new_flow
print(total)


import sys
import queue
from collections import defaultdict
(n, m) = [int(x) for x in input().strip().split(' ')]
clients = []
for _ in range(n):
	(x, y) = [int(x) for x in input().strip().split(' ')]
	clients.append((x, y))
pq_houses = queue.PriorityQueue()
for _ in range(m):
	(a, p) = [int(x) for x in input().strip().split(' ')]
	pq_houses.put((a, p))
clients = sorted(clients, key=lambda x: x[1])
buyers = [False] * n
houses_sold = 0
while not pq_houses.empty():
	(a, p) = pq_houses.get()
	for (i, c) in enumerate(clients):
		(x, y) = c
		if not buyers[i] and p <= y and (a >= x):
			buyers[i] = True
			houses_sold += 1
			break
print(houses_sold)


import bisect

def realEstateBroker(clients, houses):
	selling = []
	hi = ci = result = 0
	while ci < len(clients):
		while hi < len(houses) and clients[ci][0] >= houses[hi][0]:
			bisect.insort_left(selling, houses[hi][1])
			hi += 1
		if len(selling) > 0 and selling[-1] > clients[ci][1]:
			index = bisect.bisect_right(selling, clients[ci][1])
			if selling[index] > clients[ci][1]:
				selling.pop(index)
			else:
				selling.pop(index + 1)
			result += 1
		ci += 1
	return result
(n, m) = (int(x) for x in input().split())
clients = []
for _ in range(n):
	(x, y) = [int(a) for a in input().split()]
	bisect.insort_left(clients, (y, x))
houses = []
for _ in range(m):
	(x, y) = [int(a) for a in input().split()]
	bisect.insort_left(houses, (y, x))
print(realEstateBroker(clients, houses))


(n, m) = map(int, input().split())
(buy, house) = ([], [])
for i in range(n):
	buy.append(tuple(map(int, input().split())))
for i in range(m):
	house.append(tuple(map(int, input().split())))
buy.sort(key=lambda x: x[1])
house.sort()
sold = [False for i in range(n)]
a = 0
for h in range(m):
	for c in range(n):
		if not sold[c]:
			if buy[c][0] <= house[h][0] and buy[c][1] >= house[h][1]:
				sold[c] = True
				a += 1
				break
print(a)


from collections import defaultdict

def DFS(node):
	if node == n + m + 1:
		return 1
	visited[node] = 1
	for neighbour in graph[node]:
		if graph[node][neighbour] and (not visited[neighbour]):
			if DFS(neighbour):
				graph[node][neighbour] = 0
				graph[neighbour][node] = 1
				return 1
	return 0
(n, m) = map(int, input().split())
clients = [0 for k in range(n)]
for k in range(n):
	clients[k] = list(map(int, input().split()))
graph = [defaultdict(lambda : 0) for k in range(n + m + 2)]
for k in range(1, n + 1):
	graph[0][k] = 1
for k in range(n + 1, n + 1 + m):
	graph[k][n + m + 1] = 1
for i in range(m):
	(x, y) = map(int, input().split())
	for j in range(n):
		if x > clients[j][0] and y <= clients[j][1]:
			graph[j + 1][n + i + 1] = 1
visitedClients = [0 for k in range(n)]
visitedHouse = [0 for k in range(m)]
max_flow = 0
visited = [0 for k in range(n + m + 2)]
while DFS(0):
	max_flow += 1
	visited = [0 for k in range(n + m + 2)]
print(max_flow)


import os
import sys
from collections import defaultdict
sys.setrecursionlimit(100000000)

def BPM(u, jobs_found, seen):
	for v in range(m):
		if graph[u][v] and seen[v] == False:
			seen[v] = True
			if jobs_found[v] == -1 or BPM(jobs_found[v], jobs_found, seen):
				jobs_found[v] = u
				return True
	return False
(n, m) = list(map(int, input().split()))
clients = []
for _ in range(n):
	val = list(map(int, input().rstrip().split()))
	val = (val[0] << 30) + val[1]
	clients.append(val)
houses = []
for _ in range(m):
	val = list(map(int, input().rstrip().split()))
	val = (val[0] << 30) + val[1]
	houses.append(val)
houses.sort()
graph = []
val = 2 ** 30 - 1
for i in range(n):
	graph.append([])
	for j in range(m):
		p = clients[i] & val
		a = clients[i] >> 30
		y = houses[j] & val
		x = houses[j] >> 30
		if y <= p and x > a:
			graph[i].append(1)
		else:
			graph[i].append(0)
jobs_found = [-1 for i in range(m)]
result = 0
for i in range(n):
	seen = [False for j in range(m)]
	if BPM(i, jobs_found, seen):
		result += 1
print(result)


(p, q) = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(p)]
b = [tuple(map(int, input().split())) for _ in range(q)]
a.sort(reverse=True)
b.sort()
c = 0
for i in a:
	j = q - 1
	x = -1
	while j >= 0 and b[j][0] >= i[0]:
		if b[j][1] <= i[1] and (x < 0 or b[x][1] < b[j][1]):
			x = j
		j -= 1
	if x >= 0:
		c += 1
		b.pop(x)
		q -= 1
	if q == 0:
		break
print(c)


(n, m) = map(int, input().split())
(buy, house) = ([], [])
for i in range(n):
	buy.append(tuple(map(int, input().split())))
for i in range(m):
	house.append(tuple(map(int, input().split())))
buy.sort(key=lambda x: x[1])
house.sort()
sold = [False for i in range(n)]
a = 0
for h in range(m):
	for c in range(n):
		if not sold[c]:
			if buy[c][0] <= house[h][0] and buy[c][1] >= house[h][1]:
				sold[c] = True
				a += 1
				break
print(a)


(n, m) = map(int, input().split())
list1 = [tuple(map(int, input().split())) for _ in range(n)]
list2 = [tuple(map(int, input().split())) for _ in range(m)]
list1.sort(reverse=True)
list2.sort()
ans = 0
for i in list1:
	j = m - 1
	x = -1
	while j >= 0 and list2[j][0] >= i[0]:
		if list2[j][1] <= i[1] and (x < 0 or list2[x][1] < list2[j][1]):
			x = j
		j -= 1
	if x >= 0:
		ans += 1
		list2.pop(x)
		m -= 1
	if m == 0:
		break
print(ans)


(n, m) = map(int, input().strip().split())
a = []
p = []
for i in range(n):
	a.append(tuple(map(int, input().split())))
for i in range(m):
	p.append(tuple(map(int, input().split())))
a.sort(key=lambda x: x[1])
p.sort()
sold = [False for i in range(n)]
result = 0
for h in range(m):
	for c in range(n):
		if not sold[c]:
			if a[c][0] <= p[h][0] and a[c][1] >= p[h][1]:
				sold[c] = True
				result += 1
				break
print(result)


import os
import sys

def realEstateBroker(clients, houses):
	houses = sorted(houses)
	clients = sorted(clients, key=lambda x: x[1])
	sold = 0
	for house in houses:
		for client in clients:
			if house[0] >= client[0] and house[1] <= client[1]:
				sold += 1
				clients.remove(client)
				break
	return sold
nm = input().split()
n = int(nm[0])
m = int(nm[1])
clients = []
for _ in range(n):
	clients.append(list(map(int, input().rstrip().split())))
houses = []
for _ in range(m):
	houses.append(list(map(int, input().rstrip().split())))
result = realEstateBroker(clients, houses)
print(str(result))