题目描述

$\color{darkorange}\text{噜噜}$ 在玩一个叫做四国争霸的游戏。在这个游戏中，四个国家将在 $n \times m$ 的网格地图上占据领土。

现在 $\color{darkorange}\text{噜噜}$ 知道了这些国家计划占领的领土规划：

• 第 $i$ 个国家计划占据一个长为 $l_i$，宽为 $w_i$ 的特殊形状领土。
• 每个国家的领土必须包含一个角落【只需要占领一个角落区域，并不一定顶角的格子需要占领】。以下情况也认为是占领一个角落(左上角那片区域)：

• 领土的形状不能旋转/翻转。

$\color{darkorange}\text{噜噜}$ 想要通过合理的分配四个国家的领土位置，使得冲突领土的数量最小（一个冲突领土的定义为被多个国家占领），请你帮助他计算最小值。

输入格式

第一行两个整数 $n,m$ 代表网格地图的大小。

接下来四块： 第一行两个整数 $h_i,w_i$，表示对应国家计划占领的矩形领土长和宽。

接下来 $l_i$ 行,每行 $w_i$ 个字符，分别代表这个国家打算占领的矩形领土的具体情况。

其中 $X$ 字符代表这个国家计划占领这一块土地，$O$ 表示这个国家不打算占领这个土地。

输出格式

一个整数表示结果。

样例

3 3
2 2
X X
X O
1 2
X X
1 1
X
2 2
O X
X X

0

样例解释1

每个格子只会出现一个X,$0$冲突

4 4
3 3
X X X
X X X
X X X
2 2
X X
X X
2 3
X X X
X X X
2 1
X
X

4

提示

• 对于 $20\%$ 数据：$n = m = 3,l_i = w_i = 2$。
• 对于 $50\%$ 数据：$1 \leq n,m \leq 10,1 \leq l_i, w_i \leq 5$。
• 对于 $100\%$ 数据：$1 \leq n,m \leq 800,1 \leq l_i, w_i \leq 500$,并且数据保证所有的$l_i \lt n ,w_i \lt m$。