아이콘 한 번에 지우기

앤드루는 파일을 한 번도 지운 적이 없다. 화면은 아이콘으로 가득 찼고 원하는 파일을 찾는 데도 한참이 걸리자, 이제야 한 무더기를 정리하기로 했다.

앤드루는 마우스로 아이콘 주위에 상자를 그린 다음 삭제 키를 눌러 파일을 지운다. 아이콘의 중심이 상자 안에 있으면 그 아이콘은 상자 안에 있는 것으로 치고, 상자 안의 아이콘은 모두 지워진다. 한 번의 삭제로 끝내려면 지울 아이콘의 중심이 모두 상자 안에 있고 남길 아이콘의 중심은 하나도 상자 안에 없어야 한다.

앤드루는 아이콘을 먼저 다른 자리로 끌어다 놓아도 된다. 아이콘 하나를 끄는 것이 이동 한 번이다. 지울 아이콘을 상자 안으로 옮겨도 되고, 남길 아이콘을 상자 밖으로 옮겨도 된다.

아래 그림에서 검은 아이콘 세 개는 지울 파일이고 흰 아이콘 두 개는 남길 파일이다. 오른쪽 그림처럼 두 개를 옮기면 검은 아이콘 세 개가 한 상자 안에 모인다. 두 개를 옮기는 다른 방법도 많지만, 하나만 옮겨서는 절대 안 된다.

화면의 아이콘 배치가 주어질 때, 한 번의 삭제로 지울 파일만 정확히 지우려면 아이콘을 최소 몇 개 옮겨야 하는지 구하는 프로그램을 작성하시오.

첫째 줄에 네 정수 nr, nc, n, m이 주어진다. 화면의 세로 픽셀 수는 nr, 가로 픽셀 수는 nc이고 ($1 \le nr, nc \le 10000$), 지울 아이콘은 n개, 남길 아이콘은 m개다 ($0 \le n$, $0 \le m$, $n + m \le 100$).

이어서 정수 $2(n + m)$개가 주어진다. 앞의 n쌍은 지울 아이콘, 나머지 m쌍은 남길 아이콘이다. 각 쌍 r c는 아이콘 왼쪽 위 모서리의 행과 열이다 ($0 \le r < nr$, $0 \le c < nc$). 처음에 같은 자리에 놓인 아이콘은 없지만, 아이콘끼리 겹칠 수는 있다.

모든 아이콘은 세로 15픽셀, 가로 9픽셀이다. 왼쪽 위 모서리가 (r, c)인 아이콘은 r행부터 r+14행까지, c열부터 c+8열까지를 덮고 중심은 $(r + 7.5,\ c + 4.5)$다. 아이콘이 화면 아래쪽이나 오른쪽 경계 밖으로 걸쳐 있을 수 있고, 그러면 중심이 화면 밖에 놓인다.

앤드루는 아이콘의 픽셀이 적어도 하나 화면에 남는 자리라면 어디로든 아이콘을 옮길 수 있고, 두 아이콘이 같은 자리에 놓여도 된다.

상자는 화면 위에 그리므로 네 변이 모두 픽셀 경계에 놓인다. 위쪽 변과 아래쪽 변은 0 이상 nr 이하의 정수이고, 왼쪽 변과 오른쪽 변은 0 이상 nc 이하의 정수이며, 위쪽 변은 아래쪽 변보다 위에, 왼쪽 변은 오른쪽 변보다 왼쪽에 있다. 아이콘의 중심이 픽셀 경계에 놓이는 일은 없으므로 아이콘은 상자 안이거나 상자 밖이다. 중심이 화면 밖에 있는 아이콘은 어떤 상자 안에도 들어가지 않는다.

한 번의 삭제로 지울 아이콘 n개만 정확히 지우려고 할 때 옮겨야 하는 아이콘 개수의 최솟값을 출력한다.