31946번 - 죽음의 등굣길

문제

지훈이는 등굣길에서 보도블록을 지날 때 같은 색의 보도블록만을 밟으면서 이동한다. 왜냐하면 다른 색의 보도블록을 밟으면 사망하기 때문이다.

등굣길은 $N \times M$ 크기의 행렬로 표현할 수 있으며 행렬의 각 원소는 하나의 보도블록으로 이루어져 있다. 지훈이는 1ドル$행 1ドル$열에서 출발해 $N$행 $M$열에 도착해야 한다.

빨간색 또는 회색으로 이루어진 등굣길을 이동하면서 지훈이는 현재 밟고 있는 보도블록과 같은 색의 보도블록만을 밟고 이동해야 한다. 또한 지훈이의 점프력이 $X$이기 때문에 맨해튼 거리가 $X$ 이하인 보도블록으로만 이동할 수 있다. 지훈이가 무사히 등교를 마칠 수 있는지 알려주자.

입력

첫째 줄에 등굣길의 행의 개수 $N$이 주어진다. $(2 \le N\le 100)$

둘째 줄에 등굣길의 열의 개수 $M$이 주어진다. $(2 \le M\le 100)$

셋째 줄부터 $N$개의 줄에 걸쳐 $i + 2$번째 줄에 $i$번째 행의 보도블록의 색깔을 나타내는 $M$개의 정수가 열 순서대로 공백으로 구분되어 주어진다. 0ドル$인 경우 빨간색 보도블록, 1ドル$인 경우 회색 보도블록이라는 것을 의미한다.

마지막 줄에 지훈이의 점프력을 나타내는 정수 $X$가 주어진다. $(1 \le X \le 10)$

출력

지훈이가 살아서 등교에 성공할 수 있으면 ALIVE, 그렇지 않으면 DEAD를 출력한다.

제한

노트

$x_1$행 $y_1$열에 있는 보도블록과 $x_2$행 $y_2$열에 있는 보도블록 사이의 맨해튼 거리는 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert$로 정의한다.