27068번 - 이미지 보정 작업

문제

현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야 등 스마트 모빌리티 솔루션 연구에 강점을 갖고 있다. 자율주행 및 주행보조 성능 개선 등 소프트웨어 분야에 대한 활발한 기술 개발을 진행하고 있는 현대모비스는 차량의 카메라로 얻은 이미지를 처리하는 소프트웨어를 개발하고 있다. 특히 야간, 악천후 등의 상황에서 이미지가 선명하지 않을 수 있는데, 소프트웨어 기반의 후처리를 통해 이미지를 보정하는 것은 중요한 일이다.

차량의 카메라가 얻은 이미지 정보는 세로로 $N$칸, 가로로 $M$칸으로 분할된 총 $NM$개의 구역으로 나누어 표현할 수 있다. 각 구역 내의 이미지 정보가 얼마나 선명한지를 정수로 나타내고 이를 선명도라 부르자.

이미지의 한 구역을 보정하면 해당 구역의 선명도를 최대 선명도인 $X$로 만들 수 있다. 물론 모든 구역을 보정하면 좋겠으나, 운전자에게 이미지가 보여지기까지 시간이 많이 걸리면 불편하므로 $K$개 이하의 구역만 보정하고자 한다.

인접한 두 구역의 선명도 차이가 크다면 운전자가 보기에 이미지가 어색하기 때문에, 인접한 두 구역의 선명도의 가장 큰 차이가 최소가 되어야 한다. 만약 두 구역이 서로 변을 공유한다면, 두 구역이 인접하다고 한다.

현대모비스를 위해 $K$개 이하의 구역을 보정하여 만들 수 있는 인접한 두 구역의 선명도의 가장 큰 차이의 최솟값을 구해보자.

입력

첫째 줄에 이미지 정보의 세로 칸 개수 $N,ドル 가로 칸 개수 $M,ドル 보정할 수 있는 구역의 개수 $K,ドル 보정했을 때의 선명도 $X$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에는 각각 $M$개의 정수 $a_{i,1},a_{i,2},\cdots,a_{i,m}$이 공백으로 구분되어 주어진다. $a_{i,j}$는 이미지 정보의 위에서 $i$번째, 왼쪽에서 $j$번째 구역의 선명도를 의미한다.

출력

이미지를 보정해서 만들 수 있는 인접한 두 구역의 선명도의 가장 큰 차이의 최솟값을 출력하라.

제한

• 1ドル \le N, M \le 500$
• 0ドル \le K \le NM$
• 1ドル \le X \le 10^{18}$
• 0ドル \le a_{i,j} \le X$

힌트