2059 - 【NOIP2014】 子矩阵
Time Limit : 1 秒
Memory Limit : 128 MB
Input
第一行包含用空格隔开的四个整数 n，m，r，c，意义如问题描述中所述，每两个整数之间用一个空格隔开。
接下来的 n 行，每行包含 m 个用空格隔开的整数，用来表示问题描述中那个 n 行 m 列的矩阵。
Output
输出共 1 行，包含 1 个整数，表示满足题目描述的子矩阵的最小分值。
Examples
Input
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
Output
6
Input
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
Output
16
Hint
【输入输出样例 1 说明】
该矩阵中分值最小的 2 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、第 4 列交叉位置的元素组成，为^{6 5 6}_{7 5 6} ，其分值为6−5 + 5−6 + 7−5 + 5−6 +|6−7+5−5 + 6−6=6。
【输入输出样例 2 说明】
该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成，选取的分值最小的子矩阵为
9 7 8
9 8 8
5 8 10
【数据说明】
- 对于50%的数据，1 ≤ n ≤ 12, 1 ≤ m ≤12,矩阵中的每个元素1≤ a[i][j] ≤20;
- 对于100%的数据，1 ≤ n ≤ 16, 1 ≤ m ≤ 16,矩阵中的每个元素1 ≤ a[i][j] ≤1000, 1 ≤ r ≤ n, 1 ≤ c ≤ m。