통행료

실크로드에 강도가 늘면서 이 길을 지나는 상인이 점점 줄고 있다. 길목에 자리 잡은 강도는 지나가는 상인에게서 가능한 한 많은 돈을 빼앗는다. 그래서 상인은 이동 거리가 늘어나더라도 실크로드를 피해 다른 길을 택한다. 강도의 수입이 줄어들자 강도 두목 모라드베이그는 새로운 방식, 곧 통행료 제도를 만들었다.

이 제도에서 각 강도는 경계를 포함한 정사각형 영역 하나만 맡고, 이 영역을 그 강도의 영역이라고 부른다. 영역끼리 겹치지 않는다는 보장은 없다. 통행료는 어느 영역에서나 정확히 1 오슬룹이다. 나머지 규칙은 다음과 같다.

강도는 자기 영역 밖에서는 통행료를 받을 수 없다.
통행료를 낸 상인에게 강도는 자기 영역에만 유효한 통행권을 발급해야 한다. 상인은 이 통행권으로 그 영역 안을 다른 강도에게 통행료를 더 내지 않고 자유롭게 이동할 수 있다. 상인이 영역을 벗어나면 통행권은 곧바로 무효가 되고 다시 쓸 수 없다.
유효한 통행권이 없으면 상인은 강도의 영역을 지나갈 수 없다.
상인은 원한다면 지금 가진 통행권을 스스로 무효로 만들고, 자기가 있는 위치를 영역에 포함하는 강도에게서 새 통행권을 받을 수 있다.

부유한 상인 마르코 폴로는 실크로드의 시작점부터 끝점까지 전 구간을 지나려고 한다. 예전보다 사정이 나아졌지만 그는 여전히 통행료를 덜 내고 싶다. 마르코 폴로가 전 구간을 지나려면 내야 하는 최소 통행료를 구하는 프로그램을 작성하라. 실크로드는 직교 경로이므로 경로의 각 선분은 수평이거나 수직이다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 각 테스트 케이스의 첫 줄에는 양의 정수 $n$ 과 $m$ 이 주어진다 ( $n, m \le 1000$ ). $n$ 은 영역의 개수, $m$ 은 실크로드 꼭짓점의 개수다. 이어지는 $n$ 개의 줄에는 영역이 한 줄에 하나씩 주어진다. 각 줄에는 음이 아닌 정수 $x$ , $y$ , $k$ 가 주어지며 ( $x, y \le 10^6$ , $k \le 1000$ ), $(x, y)$ 는 영역에서 가장 아래이면서 가장 왼쪽인 꼭짓점이고 $k$ 는 영역의 한 변의 길이다. 이어지는 $m$ 개의 줄에는 실크로드 꼭짓점의 좌표가 경로에 나타나는 순서대로 주어진다. 경로는 자기 자신과 교차하지 않는다. 입력은 0 0이 적힌 줄로 끝나고, 이 줄은 처리하지 않는다.

문제

입력

출력