조용히 하라고!!

시간 제한1초메모리 제한1024 MB

요약

두 가지 모기 잡기 방법 각각에 대해 잡을 수 있는 모기의 최대 수를 구한다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 기하, 구현
정답자: 아직 제출이 없습니다

문제

1학기 기말고사 하루 전, 위기감을 느낀 1학년 나코더 반은 드디어 $N$ 행 $M$ 열의 격자로 구성된 교실에서 부랴부랴 공부하고 있다. 하지만 조용한 교실에 갑자기 $K$ 마리의 모기가 나타난 것이 아닌가!! $i (1 \leq i \leq K)$ 번째 모기는 $r$ 행 $c$ 열 위치 $(r,c)$ 에 있고 $s\_i$ 의 체력을 가지고 있다. 같은 위치에 두 마리 이상의 모기가 있을 수 있다.

앵앵거리는 소리에 짜증이 난 나코더 친구들은 모기를 몰살하고자 한다. 준비성이 철저한 우정이는 이날을 위해 태권도 선생님으로부터 태극 4장이 아닌, 태극 모기장을 전수받았다. 태극 모기장 품새의 구성은 다음과 같다.

우정이는 1초에 1칸씩 상하좌우로 움직일 수 있다.
모기가 있는 장소에 도착하면, 우정이는 즉시 모기의 체력에 관계없이 강력한 몸통 지르기로 모기를 잡는다.
하지만 우정이는 체력이 안 좋기 때문에 최대 $T$ 초 동안 움직일 수 있다. 정확히 $0$ 초나 $T$ 초가 되는 순간에도 모기를 잡을 수 있다. 같은 위치에 여러 마리의 모기가 있다면, 우정이는 모든 모기를 동시에 잡는다.
우정이의 초기 위치는 자유롭게 선택할 수 있다.

하지만 우정이의 저질 체력으로 인해 태극 모기장의 효과가 별로일 것이라 판단한 아름이는 대대로 내려오는 현대 정보과학의 결정체인 태극 전기장을 사용하려고 한다. 태극 전기장 품새의 구성은 다음과 같다.

아름이는 특정 좌표 $(R,C)$ ( $1 \leq R \leq N , 1 \leq C \leq M$ )를 지정해 세기 $P$ 의 강력한 전기장을 형성할 수 있다.
전기장이 형성되면, 교실 내의 어떤 위치 $(R', C')$ ( $1 \leq R' \leq N , 1 \leq C' \leq M, (R', C') \neq (R, C)$ )에서의 전기장의 세기는 $(R',C')$ 과 $(R,C)$ 의 택시 거리 $L$ 에 대해 $\frac{P}{L}$ 과 같다. 예외적으로, $(R,C)$ 에서의 전기장의 세기는 $10^{2024}$ 이다.
해당 위치의 전기장의 세기가 그 위치에 있는 모기의 체력보다 크거나 같다면 모기를 잡을 수 있다.

우정이와 아름이가 각각 최대로 잡을 수 있는 모기의 수를 출력하라!!

입력

첫 번째 줄에 격자판의 세로 크기 $N$ 과 가로 크기 $M$ , 모기의 수 $K$ , 우정이의 체력 $T$ 와 아름이가 형성하는 전기장의 세기 $P$ 가 공백으로 구분되어 주어진다.

이후 $K$ 줄에 걸쳐 그중 $i(1 \leq i \leq K)$ 번째 줄에 $i$ 번째 모기의 위치와 체력을 나타내는 세 정수 $r\_i$ , $c\_i$ , $s\_i$ 가 공백으로 구분되어 주어진다.

출력

우정이가 아름이가 각각 최대로 잡을 수 있는 모기의 수를 순서대로 공백으로 구분하여 출력한다.

제한

$1 \leq N, M \leq 50$
$1 \leq K \leq 10$
$1 \leq T, P \leq 10^9$
$1 \leq r\_i \leq N (1 \leq i \leq K)$
$1 \leq c\_i \leq M (1 \leq i \leq K)$
$1 \leq s\_i \leq 30 (1 \leq i \leq K)$
문제에서 주어지는 모든 수는 정수이다.

힌트

$(r\_1,c\_1)$ 과 $(r\_2,c\_2)$ 사이의 택시 거리 $d$ 는 다음과 같이 정의된다: $d = \left\vert r\_1-r\_2 \right\vert + \left\vert c\_1-c\_2 \right \vert$

예제1

예제 1
입력
```
4 4 2 6 6
1 2 18
3 1 22
```
예상 출력
```
2 1
```