조용히 하라고!!

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

요약

격자에 모기가 최대 10마리 있을 때, 한 사람이 T초 안에 잡을 수 있는 최대 수와 한 지점의 전기장이 닿는 최대 수를 구합니다.

난이도: 보통10점 중 5점
유형: 비트 연산, BFS, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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)$ )에서의 전기장 세기는 두 위치의 택시 거리 $L$ 에 대해 $\frac{P}{L}$ 이다. 예외적으로 $(R,C)$ 에서의 전기장 세기는 $10^{2024}$ 이다.
어떤 위치의 전기장 세기가 그 위치에 있는 모기의 체력보다 크거나 같으면, 아름이는 그 모기를 잡을 수 있다.

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

입력

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

이후 $K$ 줄에 걸쳐 $i$ 번째 줄에는 $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 = |r_1-r_2| + |c_1-c_2|$ 로 정의된다.

예제1

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