Image Correction Task

Time limit3sMemory limit1024 MB

Summary

Given a grid of sharpness values, correct at most K cells to the maximum X so the largest difference between adjacent cells is as small as possible.

Level: Hard8 of 10
Topics: Binary search, Graph
Solved: No attempts yet

Problem

Hyundai Mobis is a global auto parts company with strong research in smart mobility, including autonomous driving, connectivity, and electrification. The company develops software for autonomous driving and driver assistance, including software that processes images from vehicle cameras. Images can be unclear at night or in bad weather, so correcting images with software after capture matters.

An image from a vehicle camera can be split into $N$ rows and $M$ columns, giving $NM$ regions in total. The clarity of the image in each region is an integer called sharpness.

Correcting one region sets its sharpness to the maximum sharpness $X$ . Ideally every region would be corrected, but the driver waits too long if correction takes time, so at most $K$ regions are corrected.

If two adjacent regions differ a lot in sharpness, the image looks unnatural to the driver. Two regions are adjacent if they share an edge. The largest sharpness difference between adjacent regions should be as small as possible.

Find the minimum possible value of the largest sharpness difference between adjacent regions after correcting at most $K$ regions.

Input

The first line contains $N$ , $M$ , $K$ , and $X$ , separated by spaces. Each of the next $N$ lines contains $M$ integers $a_{i,1}, a_{i,2}, \cdots, a_{i,M}$ , separated by spaces. $a_{i,j}$ is the sharpness of the region in row $i$ from the top and column $j$ from the left.

Output

Print the minimum possible value of the largest sharpness difference between adjacent regions after correction.

Constraints

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

Examples3

Example 1
Input
```
2 4 2 3
2 0 2 2
1 2 3 1
```
Expected output
```
1
```
Example 2
Input
```
1 3 1 10
1 5 9
```
Expected output
```
4
```
Example 3
Input
```
1 1 0 5
1
```
Expected output
```
0
```