이미지 보정 작업

시간 제한3초메모리 제한1024 MB

요약

격자의 선명도가 주어질 때, 최대 K개의 칸을 X로 바꿔 인접한 칸끼리의 최대 차이를 가장 작게 만드는 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 그래프
정답자: 아직 제출이 없습니다

문제

현대모비스는 자율주행, 커넥티비티, 전동화 등 스마트 모빌리티 연구에 강점이 있는 글로벌 자동차 부품 기업이다. 자율주행과 주행보조 소프트웨어를 개발하고 있으며, 차량 카메라로 얻은 이미지를 처리하는 소프트웨어도 함께 개발하고 있다. 야간이나 악천후에서는 이미지가 선명하지 않을 수 있어서, 소프트웨어로 후처리해 이미지를 보정하는 일이 중요하다.

차량 카메라의 이미지 정보는 세로 $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$

예제3

예제 1
입력
```
2 4 2 3
2 0 2 2
1 2 3 1
```
예상 출력
```
1
```
예제 2
입력
```
1 3 1 10
1 5 9
```
예상 출력
```
4
```
예제 3
입력
```
1 1 0 5
1
```
예상 출력
```
0
```