전쟁 - 불 대신 물

불을 이용한 공격은 강력하지만, 적군은 이미 그 가능성을 예상하고 나무가 없는 곳에 진을 쳤다. 그래서 이번에는 물을 흘려 적군이 있는 위치를 잠기게 하려고 한다.

N * N 크기의 지도가 있다. 적군은 (x, y)에 있고, 물은 (1, 1)에서 흘려보낸다. 각 칸에는 땅이 파여 있는 깊이가 주어진다. 어떤 칸에 물이 있을 때, 네 방향으로 인접한 칸 중 현재 높이가 더 낮은 칸이 있으면 물은 그 칸으로 흐른다. 여기서 현재 높이는 그 칸의 깊이와 이미 차 있는 물의 높이를 함께 고려한 값이다.

물은 더 이상 어떤 칸에서도 다른 방향으로 흐를 수 없을 때까지 이동한다. 적군이 있는 칸에 높이 k 이상의 물이 확실히 차도록 하려면, 최소 얼마의 물을 흘려야 하는지 구하시오.

첫째 줄에 지도의 크기 N과 적군이 있는 칸에 채워야 하는 물의 높이 k가 주어진다. N <= 400, k <= 1,000,000이다.

둘째 줄에 적군의 위치 x y가 주어진다.

셋째 줄부터 N개의 줄에는 각 칸의 깊이가 주어진다. 깊이는 1,000,000을 넘지 않는다.

흘려야 하는 물의 최소 양을 출력한다.

물을 흘린 뒤 안정화될 수 있는 상태가 여러 가지라면, 어느 상태가 될지 알 수 없다. 따라서 적군이 있는 칸이 높이 k만큼 확실히 잠기는 최소 물의 양을 구해야 한다.

물은 N * N 지도 밖으로 빠져나가지 않는다고 보아도 된다.