폐쇄회로 감시
시간 제한2초메모리 제한128 MB
볼록 n각형과 비용이 있는 m개의 외부 카메라 후보 지점이 주어질 때, 모든 벽이 (동일 직선상은 제외하고) 최소 하나의 카메라에 감시되도록 설치 비용의 총합을 최소화하고 불가능하면 -1을 출력하는 문제입니다.
문제
볼록 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을 출력한다.