미르코와 슬라브코는 동물 모양의 장난감을 갖고 놀고 있다.

노는 방법은 다음과 같다.

먼저 아래 그림과 같은 두 개의 게임판(1~2차원 칸으로 된 균일 간격 격자) 중 하나를 고른다.

그리고 게임판 내부 임의의 칸(그림에서 동그라미로 표현된)에 N개의 동물 장난감을 집어넣는다.

그림에서 보다시피 어떤 칸에서 인접한 칸은 각 차원의 축과 평행한 선분으로만 연결되어 있는데,

두 칸의 ‘거리’는 다른 칸으로 가기 위해 거쳐야 하는 선분의 최소 개수로 정의된다.

다시 말해 2차원을 예로 들 때 임의의 위치에 있는 칸 A(x1, y1)와 B(x2, y2)의 거리는 단순히 |x1-x2|+|y1-y2|가 되며,

1차원의 경우도 같은 계산법이 성립한다는 뜻이다.

게임판에서 서로 거리가 D 이하인 칸에 있는 두 동물은 울음소리를 통해 상대방을 알아차릴 수 있다.

슬라브코는 이렇게 서로 알아차릴 수 있는 동물의 쌍이 얼마나 되는지 알고 싶어 한다.

게임판의 종류, 그 게임판에 있는 모든 동물들의 위치와 최장 가청 거리 D 값을 입력 받아

서로 충분히 가까이 있는 동물의 쌍이 얼마나 있는지 찾는 프로그램을 작성하시오.

가까운 짝 찾기(Pairs) 1 timer 1s memory 256MB

가까운 짝 찾기(Pairs) 1 1s 256MB