빨간점, 파란점 3
시간 제한1초메모리 제한1024 MB
빨간 점들이 모두 한쪽 반평면에 들어가도록 직선을 그을 때, 반대쪽에 놓이는 파란 점들 힘의 합이 최대가 되는 값을 구합니다.
문제
평면 위에 개의 빨간 점과 개의 파란 점이 있다. 번째 파란 점은 힘 를 가지고 있다.
파란 점들이 빨간 점들을 공격하기 시작했다. 빨간 점들은 공격을 막기 위해 직선을 하나 그어 보호 구역을 정하려고 한다. 직선이 만드는 두 반평면 중 하나를 고르면, 그 반평면과 직선 위가 보호 구역이 된다. 모든 빨간 점은 보호 구역 안에 있어야 한다.
빨간 점들은 모든 파란 점을 보호 구역 밖으로 몰아낼 수는 없다. 그래서 보호 구역 안의 파란 점들의 힘을 최대한 약하게 만들려고 한다. 보호 구역 밖에 있는 파란 점들의 힘의 합이 최대가 되도록 구역을 정하라.
입력
첫 번째 줄에 양의 정수 과 이 공백으로 구분되어 주어진다.
다음 개의 줄에는 각 빨간 점의 x좌표와 y좌표가 공백으로 구분되어 주어진다.
다음 개의 줄에는 파란 점 의 x좌표, y좌표, 힘 가 공백으로 구분되어 주어진다.
모든 좌표는 절댓값이 이하인 정수이다. 좌표가 같은 두 점은 없다. 세 점이 한 직선 위에 있는 입력은 주어지지 않는다.
출력
직선을 하나 그어서 보호 구역 밖으로 내보낼 수 있는 파란 점들의 힘의 합의 최댓값을 출력한다. 파란 점을 보호 구역 밖으로 내보낼 수 없는 경우에는 을 출력한다.