피자 배달
시간 제한1초메모리 제한128 MB
M개 후보지 중 최대 K곳을 선택해 반경 R 안의 건물 인구 합(중복 제외)을 최대화하는 문제입니다.
문제
피코는 배달 피자 식당을 여러 곳 열려고 한다. 식당을 열 수 있는 후보 위치가 M개 있고, 주변에는 사는 사람 수가 알려진 주거 건물 N개가 있다.
식당 하나는 그 식당과의 유클리드 거리가 R 이하인 모든 주거 건물에 배달할 수 있다. 피코는 후보 위치 중 최대 K곳에 식당을 열 수 있다. 한 주거 건물이 여러 식당의 배달 범위에 포함되더라도 그 건물의 사람 수는 한 번만 센다.
배달 범위에 포함할 수 있는 사람 수의 최댓값을 구하라.
입력
첫째 줄에 열 수 있는 식당 수의 상한 K와 배달 반경 R이 공백으로 구분되어 주어진다 (1 <= K <= 10, 1 <= R <= 500).
둘째 줄에 식당 후보 위치의 수 M이 주어진다 (K <= M <= 20).
다음 M개의 줄에는 각 후보 위치의 좌표를 나타내는 두 정수 X, Y가 공백으로 구분되어 주어진다 (-1000 <= X, Y <= 1000).
그다음 줄에 주거 건물의 수 N이 주어진다 (1 <= N <= 100).
다음 N개의 줄에는 세 정수 X, Y, S가 공백으로 구분되어 주어진다. X와 Y는 주거 건물의 좌표이고, S는 그 건물에 사는 사람 수이다 (-1000 <= X, Y <= 1000, 1 <= S <= 100). 주거 건물과 식당 사이의 거리가 R 이하이면 그 주거 건물은 그 식당의 배달 범위에 포함된다.
식당 후보 위치 중 같은 좌표를 가진 두 위치는 없다.
출력
배달 범위에 포함할 수 있는 사람 수의 최댓값을 정수 하나로 출력한다.