32983번 - 동굴

문제

젤다는 처음으로 모험을 떠나 들뜬 마음으로 하이랄 왕국을 구하기 위해 동분서주하고 있다. 그러나 현실은 녹록지 않다. 모험 자금을 마련하기 위해 루피(화폐 단위)를 모으는 데 열중할 수밖에 없었다.

어느 날, 젤다는 어두운 동굴을 발견했다. 동굴 안에는 루피가 흩어져 있지만 너무 어두워 램프를 이용해 빛을 밝혀 루피를 모으고 싶다. 동굴은 $N \times M$ 크기의 격자로 이루어져 있으며 위에서부터 $r$번째, 왼쪽에서부터 $c$번째에 위치한 칸을 $(r,c)$로 나타낸다. 일부 칸은 벽으로 막혀 있어 젤다가 이동하거나 램프 빛이 통과할 수 없다.

램프는 동굴 입구인 $(S_r, S_c)$에 고정되어 있으며, 젤다는 램프를 들고 이동할 수 없다. 다만 램프 빛의 세기를 음이 아닌 정수 $L$로 자유롭게 설정할 수 있다. 램프 빛의 세기가 $L$인 경우 램프가 놓인 위치에서 최단 거리가 $L$이하인 모든 칸을 밝힌다. 최단 거리는 출발 칸을 제외하고, 상하좌우로 인접한 칸을 지나 도착 칸까지 이동할 때 지나야 하는 최소 칸의 개수이다. 젤다는 램프 빛이 밝히고 있는 모든 칸의 루피를 얻을 수 있으나, 설정한 램프 빛의 세기에 따라 비용이 발생한다. 비용은 빛의 세기 1ドル$당 단위 비용 $C$가 발생한다. 만약 램프 빛의 세기를 $L$로 설정한다면 젤다는 $L \times C$만큼 비용을 소모하게 된다.

소모한 비용을 $L \times C$ 얻은 루피의 합을 $T$라 할 때, 젤다가 얻는 이윤은 $T-L \times C$이다. 젤다는 동굴에서 자신이 얻을 수 있는 최대 이윤을 알고 싶다. 모험 중이라 바쁜 젤다는 당신에게 이 일을 부탁했다. 젤다를 도와 동굴에서 얻을 수 있는 최대 이윤을 구해보자.

입력

첫 번째 줄에 동굴의 행, 열의 크기 $N$과 $M,ドル 램프 빛의 세기 당 비용 $C$가 공백으로 구분되어 주어진다. $(2\leq N,M \leq 1,000円; 1\leq C \leq 100)$

두 번째 줄에 램프가 고정되어 있는 시작 위치 $S_r,ドル $S_c$가 공백으로 구분되어 주어진다. $(1\leq S_r \leq N; 1\leq S_c \leq M)$

세 번째 줄부터 동굴의 정보가 $N$개의 줄에 걸쳐 한 줄에 $M$개씩 공백으로 구분되어 주어진다. 수는 1ドル,000円$보다 작거나 같은 음이 아닌 정수 또는 $-1$로 구성되며 $-1$인 경우는 통과할 수 없는 벽을, 나머지는 해당 칸에서 얻을 수 있는 루피를 나타낸다. 램프가 있는 시작 위치에는 벽이 존재하지 않지만, 루피는 존재할 수 있다. 또한 격자 밖은 모두 벽으로 이루어져 있어 젤다가 이동하거나 램프 빛이 통과할 수 없다.

출력

램프 빛의 세기를 조절하여 젤다가 얻을 수 있는 최대 이윤을 출력한다. 얻을 수 있는 이윤이 없다면 0ドル$을 출력한다.

제한

힌트