폐쇄회로 감시

볼록 n각형 모양의 건물이 있다. 건물 밖에 CCTV를 설치해 건물의 모든 외벽을 감시하려고 한다. CCTV는 미리 주어진 m개의 외부 위치에만 설치할 수 있다.

그림 1	그림 2	그림 3

그림 1처럼 설치 가능한 위치들이 주어졌다고 하자. 1번 위치에 CCTV를 설치하면 그림 2에서 빨간색으로 표시된 두 외벽을 감시할 수 있다. 단, CCTV와 외벽이 같은 직선 위에 있으면 그 외벽은 감시할 수 없다고 본다. 예를 들어 6번 위치에 CCTV를 설치하면 그림 3에서 파란색으로 표시된 외벽은 감시하지 못한다.

여러 위치에 CCTV를 설치하면 모든 외벽을 감시할 수 있다. 그림 1의 경우 1, 2, 4, 6번 위치에 설치하거나 그림 4처럼 설치해도 되고, 1, 3, 5, 7번 위치에 설치하면 그림 5처럼 모든 외벽을 감시할 수 있다.

그림 4	그림 5

각 위치마다 CCTV 설치 비용이 다르다. 모든 외벽을 감시할 수 있도록 CCTV를 설치할 때 필요한 최소 비용을 구하라.

첫째 줄에 자연수 n과 m이 주어진다. 여기서 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000이다.

다음 n개 줄에는 다각형의 꼭짓점 좌표 x, y가 반시계 방향 순서로 하나씩 주어진다. 그 다음 m개 줄에는 CCTV를 설치할 수 있는 위치의 x좌표, y좌표, 그리고 그 위치의 설치 비용이 차례로 주어진다.

모든 수는 공백으로 구분된다. 모든 좌표는 절댓값이 100,000을 넘지 않는 정수이고, 설치 비용은 100,000 이하의 자연수이다. 다각형에서 인접한 두 변이 같은 직선 위에 놓이는 경우는 없다.

모든 외벽을 감시할 수 있도록 CCTV를 설치하는 최소 비용을 출력한다. 그런 설치 방법이 없다면 -1을 출력한다.