공유 자전거 임시 반납소 두 곳

문제

공유 자전거 운영팀은 행사 기간에 사용할 임시 반납소를 정확히 두 곳 설치하려 한다. 설치 가능한 후보지는 M곳이며, 각 후보지에는 입력 순서대로 1번부터 M번까지 번호가 붙어 있다. 또한 행사장 주변에는 반납 수요가 발생하는 지점 N곳이 있다. 각 수요 지점에는 위치와 그곳에서 반납소를 이용하려는 사람 수가 주어진다. 행사장 주변의 길은 가로와 세로 방향으로만 이어진다고 가정한다. 좌표가 각각 (x, y), (u, v)인 두 위치 사이의 이동 거리는 |x-u|+|y-v|다. 여기서 |a|는 정수 a의 절댓값이다. 어떤 수요 지점에서 설치한 반납소 중 적어도 한 곳까지의 이동 거리가 R 이하이면, 운영팀은 그 지점의 수요를 모두 처리할 수 있다고 판단한다. 거리가 정확히 R인 경우도 처리할 수 있다. 각 반납소의 수용량에는 제한이 없다. 따라서 한 반납소가 여러 수요 지점을 함께 담당해도 된다. 다만 같은 수요 지점이 두 반납소 모두에서 R 이내에 있더라도 그 지점의 사람 수는 한 번만 더한다. 두 반납소 중 어느 곳에서도 R 이내에 있지 않은 지점은 처리 인원에 포함하지 않는다. 서로 같은 좌표에 여러 수요 지점이 주어지면 각각 별도의 수요이므로 각각의 사람 수를 더한다. 운영팀은 처리할 수 있는 사람 수의 합이 최대가 되도록 서로 다른 후보지 두 곳을 선택한다. 후보지 번호를 작은 것부터 a, b라고 할 때 최대 합을 만드는 선택이 여러 개라면 a가 가장 작은 것을 선택하고, a도 같다면 b가 가장 작은 것을 선택한다. 후보지는 항상 두 곳 이상 주어지므로 선택 자체가 불가능한 경우는 없다. 모든 선택의 처리 인원이 0명이어도 같은 동점 규칙을 적용한다. 최대 처리 인원과 선택할 두 후보지 번호를 구한다.

입력

첫째 줄에 정수 M, N, R이 공백으로 구분되어 주어진다. 2 ≤ M ≤ 50, 1 ≤ N ≤ 150, 0 ≤ R ≤ 200이다.
다음 M개 줄에 후보지의 정수 좌표 x, y가 주어진다. 서로 다른 후보지의 좌표는 서로 다르다.
다음 N개 줄에 수요 지점의 정수 좌표 x, y와 사람 수 w가 주어진다.
모든 좌표는 -100 이상 100 이하의 정수이며, w는 1 이상 1,000 이하의 정수다. 수요 지점의 좌표는 서로 같을 수 있고 후보지의 좌표와 같을 수도 있다.

출력

최대 처리 인원, 선택한 작은 후보지 번호 a, 큰 후보지 번호 b를 한 줄에 공백으로 구분하여 정수로 출력한다. 여러 선택의 처리 인원이 같으면 a가 작은 것을, a도 같으면 b가 작은 것을 출력한다.

3 4 1
0 0
3 0
0 3
0 1 4
1 0 3
3 1 6
0 3 5

13 1 2

3 2 0
0 0
2 0
4 0
1 1 7
3 1 9

0 1 2

3 3 2
0 0
2 0
8 0
1 0 10
0 1 4
8 1 6

20 1 3

출처: Devin.KR 자체 제작