Description

Definitions:

1. Submatrix: A new matrix formed by selecting some rows and some columns from a matrix and taking the elements at their intersections (preserving the relative order of rows and columns) is called a submatrix of the original matrix.

   For example, in the table below, selecting rows $2,4$ and columns $2,4,5$ yields a $2 \times 3$ submatrix as follows.

One of its $2\times3$ submatrices is:

2. Adjacent elements: An element in the matrix is adjacent to its four neighbors above, below, left, and right (if they exist).

3. Score of a matrix: The sum of the absolute differences of every pair of adjacent elements in the matrix.

Task: Given a positive-integer matrix with $n$ rows and $m$ columns, choose an $r$-row $c$-column submatrix from it so that the score of this submatrix is minimized, and output that score.

Input Format

The first line contains four integers $n, m, r, c$ separated by single spaces, as described above.

The next $n$ lines each contain $m$ integers, representing the $n$-row $m$-column matrix described in the problem statement.

Output Format

Output a single integer, the minimum possible score among all submatrices that satisfy the description.

5 5 2 3
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1

6

7 7 3 3  
7 7 7 6 2 10 5
5 8 8 2 1 6 2 
2 9 5 5 6 1 7 
7 9 3 6 1 7 8 
1 9 1 4 7 8 8 
10 5 9 1 1 8 10
1 3 1 5 4 8 6

16

Hint

Sample 1 explanation

In this matrix, the $2$-row $3$-column submatrix with the minimum score is formed by the intersection of rows $4, 5$ and columns $1, 3, 4$ of the original matrix, namely:

Its score is $|6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6$.

Sample 2 explanation

In this matrix, the $3$-row $3$-column submatrix with the minimum score is formed by the intersection of rows $4, 5, 6$ and columns $2, 6, 7$ of the original matrix. The chosen submatrix with the minimum score is:

Constraints

• For $50\%$ of the testdata, $1 \leq n \leq 12$, $1 \leq m \leq 12$, and for every element $1 \leq a_{i,j} \leq 20$.
• For $100\%$ of the testdata, $1 \leq n \leq 16$, $1 \leq m \leq 16$, every element satisfies $1 \leq a_{i,j} \leq 1000$, $1 \leq r \leq n$, and $1 \leq c \leq m$.

Translated by ChatGPT 5