题目描述

有一块地，大小为 $r \times s$，$\rm Matej$ 想买下它。这块地每个 $1\times1$ 的正方形都有不同的价格。

设一片非空子矩阵价格总和为 $m$，则这片子矩阵的权值为 $|m-a|+|m-b|$，您需要找到最小权值的子矩阵。

您只需要输出最小权值即可。

输入格式

第一行包含四个正整数 $r$, $s$ , $a$ 和 $b$ 。

下面 $r$ 行，第 $i$ 行，有 $s$ 个正整数，第 $j$ 个数表示 $c_{i,j}$，表示价格。

输出格式

一行一个整数 $v$，表示最小非空子矩阵的权值。

2 2 10 10
1 3
4 1

2

3 2 3 4
1 9
1 1
8 1

3

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

2

提示

样例解释 2

如图，总价格是$1 + 1 = 2$，这块地的权值是 $|3−2| + |4−2| =3$。

数据范围：

对于 $14\%$ 的数据：$1\le r,s\le20$

对于 $28\%$ 的数据：$1\le r,s\le100$

对于 $100\%$ 的数据：$1\le r,s\le500$，$1\le a,b,c_{i,j}\le10^9$

本题分值与 COCI 2021-2022#6 分值相同，满分 $70$ 分