동굴

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

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

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

얻은 루피의 합을 $T$라 하면 젤다의 이윤은 $T-L \times C$이다. 젤다가 동굴에서 얻을 수 있는 최대 이윤을 구해 보자.

첫 줄에 $N$, $M$, $C$가 공백으로 구분되어 주어진다. $(2 \le N,M \le 1000; 1 \le C \le 100)$

둘째 줄에 램프가 고정된 시작 위치 $S_r$, $S_c$가 공백으로 구분되어 주어진다. $(1 \le S_r \le N; 1 \le S_c \le M)$

셋째 줄부터 $N$개의 줄에 걸쳐 동굴 정보가 한 줄에 $M$개씩 공백으로 구분되어 주어진다. 각 값은 1000 이하의 음이 아닌 정수 또는 $-1$이다. $-1$은 통과할 수 없는 벽을 뜻하고, 나머지는 해당 칸에서 얻을 수 있는 루피의 양이다. 램프가 있는 시작 위치에는 벽이 없지만 루피는 있을 수 있다. 격자 밖은 모두 벽이어서 젤다와 램프 빛 모두 통과할 수 없다.

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