Minimum Submatrix Score

You are given an n by m matrix of positive integers and two integers r and c. A submatrix is defined as follows:

• Submatrix: A submatrix is obtained by choosing some rows and some columns from the original matrix (keeping their original relative order). For example, selecting the 2nd and 4th rows and the 2nd, 4th, and 5th columns (indices are 1-based) from a matrix forms a submatrix of size 2×3.
• Adjacent Elements: Two elements in a matrix are adjacent if one is directly above, below, to the left, or to the right of the other (if such a neighbor exists).
• Matrix Score: The score of a matrix is defined as the sum of the absolute differences of every pair of adjacent elements. In other words, for every pair of adjacent cells in the matrix, add \(|a - b|\) to the score.

Your task is to select an r×c submatrix from the given matrix (by choosing r rows and c columns, not necessarily consecutive) such that its score is minimized, and then output that minimum score.

The absolute difference between two numbers a and b is given by \(|a - b|\). The adjacent pairs in the submatrix are considered along its consecutive rows and columns.

inputFormat

The first line of input contains four integers n, m, r, and c where:

• n is the number of rows in the matrix.
• m is the number of columns in the matrix.
• r is the number of rows to select for the submatrix.
• c is the number of columns to select for the submatrix.

The next n lines each contain m positive integers, representing the matrix.

outputFormat

Output a single integer — the minimum score of any r×c submatrix extracted from the given matrix.

sample

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

8