25919번 - Lost Edge

새로운 RPG게임인 Lost Edge에는 레이드 시스템이 존재한다. 하지만, 레이드에 참가하기 위해선 일정 레벨 이상을 찍고 레이드 장소에 모여야 한다.

플레이어는 상하좌우 4방향으로 한 칸씩만 움직일 수 있으며, 벽은 지나갈 수 없다. 다행히도 arc가 아니기 때문에 이동 방향에 제약은 없으며, 한 번 방문한 칸도 다시 방문할 수 있다.

플레이어는 자신보다 레벨이 낮은 몬스터만 잡을 수 있다. 이때 잡은 몬스터의 레벨만큼의 경험치를 얻는다. 또한 현재 레벨이 $i$이고 $j$만큼의 경험치를 가지고 있다면, 레벨업을 위해 경험치가 $(i-j)$만큼 필요하다. 이때 레벨업을 하고 남은 경험치는 잃지 않고 남는다. 즉, $(i-j+k)$만큼의 경험치를 얻었다면 레벨업을 한 후 경험치가 $k$만큼 남게 된다. 한 번 잡은 몬스터는 다시 잡을 수 없다.

이미 잡은 몬스터가 있는 구역은 언제든 지나갈 수 있지만, 잡을 수 없는 몬스터가 있는 구역이나 레이드 장소는 지나갈 수 없다. 플레이어의 시작 장소와 레이드 장소는 유일하다.

플레이어가 원하는 레벨을 찍고 레이드 장소에 도착할 수 있을지 알아보자.

맵의 크기는 $N\times M$이다.

플레이어의 시작 레벨 $L$, 시작 경험치 $E$, 목표 레벨 $K$가 주어진다.

맵이 주어진다. 이때 플레이어의 초기 위치는 $-3$, 레이드 장소는 $-2$, 벽은 $-1$, $x$레벨 몬스터는 $x$, 나머지 빈 공간은 $0$으로 주어진다.

이때, 입력은 아래와 같이 주어진다.

플레이어가 목표 레벨에 도달하고 레이드 장소로 갈 수 있으면 O, 아니면 X를 출력한다.

• $2 \leq N$, $M \leq 100$
• $2 \leq L \leq 10\,000$
• $0 \leq E \lt L$
• $L \leq K \leq 10\,000$
• $1 \leq x \leq 10\,000$