测试数据来自 system/3051

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　先给出下面几个概念：
　　邻元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
　　矩阵得分：矩阵中每一对邻元素之差的绝对值之和。下面矩阵得分为：|9-7|+|7-8|+|9-8|+|8-8|+|5-8|+|8-10|+|9-9|+|7-8|+|8-8|+|9-5|+|8-8|+|8-10|=16。

　　真子矩阵：从原矩阵中选取某些行和某些列交叉位置的元素组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个真子矩阵。例如，下面左图中选取第2行、第4行和第2列、第4列、第5列交叉位置的元素得到一个2行3列的真子矩阵，如下图所示。

　　现在给定一个\(M\)行\(N\)列的正整数矩阵，请你从求出一个\(R\)行\(C\)列的真子矩阵，使得这个真子矩阵得分最小。

【输入格式】

　　第一行包含用空格隔开的四个整数 \(M,N,R,C（1≤M,N≤16，1≤R≤M，1≤C≤N）\)，它们意义见题目描述。接下来是一个\(M\)行\(N\)列的整数矩阵。整数之间用一个空格隔开。

【输出格式】

　　输出一个整数，表示所求真子矩阵的最小得分。

【输入输出样例1】

　Input

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

　Output

6

【输入输出样例1说明】

　　得分最小的2行3列的真子矩阵由原矩阵的第3行、第5行与第1列、第3列、第4列交叉位置的元素组成：

　　其分数为：\(|5-4| + |4-5| + |6-4| + |4-5| + |5-6| + |4-4| + |5-5| = 6\)。

【输入输出样例2】

　Input

6 6 2 4
17 8 3 9 19 10
1 5 3 10 17 10
5 16 3 7 18 9
12 1 7 18 11 7
14 1 4 7 18 11
4 17 1 3 17 16

　Output

25

【数据说明】

　　测试点1~10满足：\(1≤M,N≤12\)，矩阵中的每个元素位于区间[1,20]。
　　测试点11~20满足：\(1≤M,N≤16\)，矩阵中的每个元素位于区间[1,1000]。

【来源】

　　Mr.he