시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB528754417.600%

문제

쌍둥이 마을은 두 마을의 사람들 간에 커뮤니케이션과 문화적 교류를 위해서 만든 것이다.

따라서 정부는 마을 사이에 쌍둥이 마을을 많이 제정하려고 한다. 물론 가능한 모든 마을의 쌍을 쌍둥이 마을로 제정하면 좋겠지만, 다음과 같은 규칙을 지켜야 한다.

  1. 각 마을은 P개 이하의 쌍둥이 마을을 가진다. 쌍둥이 마을이 없을 수도 있다.
  2. 각 쌍둥이 마을의 거리는 적어도 D이다.두 마을이 (x1, y1) 과 (x2, y2) 에 있을 때, 두 마을 사이의 거리는 |x1-x2| + |y1-y2|이다.

정부는 되도록이면 많은 쌍둥이 마을을 만들려고 한다. 만약 이러한 것이 여러 가지라면, 쌍둥이 마을 사이의 거리의 합을 최소로하는 것을 선택한다. 각 마을의 위치와 P와 D가 주어질 때, 쌍둥이 마을의 개수의 최댓값과 그 때 쌍둥이 마을 사이의 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 마을의 좌표가 주어진다. x좌표와 y좌표 순서대로 주어지며, 각 좌표는 1,000보다 작거나 같은 자연수 또는 0이다. 마지막 줄에는 P와 D가 주어진다. P는 3보다 작거나 같은 자연수이고, D는 2,000보다 작거나 같은 자연수이다. 두 도시의 위치가 중복되는 경우는 없다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

3
0 0
0 10
10 4
1 11

예제 출력 1

1 14

예제 입력 2

3
0 0
0 10
10 4
1 1

예제 출력 2

1 10

예제 입력 3

4
0 0
10 0
0 20
10 20
1 1

예제 출력 3

2 20

예제 입력 4

4
0 0
10 0
0 20
10 20
2 10

예제 출력 4

4 60

예제 입력 5

9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
3 6

예제 출력 5

6 40

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: wider93