34409번 - 무등산 등반

문제

전남대학교는 광주를 대표하는 지방 거점 국립대학이다. 전남대학교에서 대중교통으로 갈 수 있는 곳이 많은데, 그 중에는 광주 지역의 명산인 무등산이 있다. 평소 산을 좋아하는 근성은 3주 간의 기초군사훈련으로 단련된 자신의 체력을 자랑하기 위해 친구들과 함께 무등산에 오를 것을 결심했다.

근성은 무등산에 오르기 이전, 무등산의 높이 정보가 적힌 지도를 입수했다. 무등산은 지도에서 세로로 $N$칸, 가로로 $M$칸인 직사각형 격자 형태로 나타난다. 지도의 가장 왼쪽 상단은 $(1, 1),ドル 가장 오른쪽 하단은 $(N, M)$으로, 근성과 친구들은 지도의 $(x, y)$ 위치에서 등반을 시작한다.

무등산의 각 칸에서는 시간을 소모하여 상하좌우로 인접한 칸 중 하나로 이동할 수 있다. 이때, 이동하는 칸의 높이 차이에 따라 이동 시간이 다르게 걸리거나 이동할 수 없는 칸이 생긴다.

• 높이 차이가 나지 않는 칸으로 이동할 때, 1ドル$분의 시간이 소모된다.
• 높이가 더 높은 칸으로 이동할 때, 두 칸의 높이 차이 1ドル$당 $a$분의 시간이 소모된다.
• 높이가 더 낮은 칸으로 이동할 때, 두 칸의 높이 차이 1ドル$당 $b$분의 시간이 소모된다.
• 높이 차이가 $c$보다 더 큰 칸으로는 이동할 수 없다.

근성이 가야 할 무등산 정상은 지도에서 높이가 가장 높은 칸이며 유일하다. 근성이 입수한 정보를 활용해 무등산 정상까지 도달하기 위한 최소 시간을 구해보자.

입력

첫 번째 줄에 지도의 세로 및 가로 크기 $N,ドル $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 근성이 등반을 시작하는 최초 위치 $x,ドル $y$가 공백으로 구분되어 주어진다.

세 번째 줄에 $a,ドル $b,ドル $c$가 공백으로 구분되어 주어진다.

네 번째 줄부터 $N$개의 줄에 걸쳐 정수 $M$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 지도에서 $(i, j)$ 위치의 높이를 의미한다. 각 값은 1ドル$ 이상 1187ドル$ 이하이다.

출력

무등산 정상에 도달하기 위해 필요한 최소 시간을 분 단위로 출력한다.

만약 정상에 도달하는 경로가 없다면, -1을 출력한다.

제한

• 1ドル \le N, M \le 500$
• $N \times M \ge 2$
• 1ドル \le x \le N; 1 \le y \le M$
• 1ドル \le a, b \le 10$
• 0ドル \le c \le 1 ,円 187$
• 입력으로 주어지는 모든 수는 정수이다.
• 근성이 등산을 시작하는 칸은 무등산 정상이 아니다.
• 지도에서 무등산 정상은 유일하다.

노트