题目描述

你可以控制云层。现在你正在观察一片大小为 $N \times M$ 的沙漠，并将其划分成边长为 $1$ 的方格。

每个格子要么是空的沙地，要么有人类居住。当两个边相邻的格子里都有人时，我们称它们属于同一个部落。换句话说，一个部落就是这张表格中由有人格子构成的一个连通块。

你想给尽可能多的部落降雨供水。你可以选择创建一个大小为 $H \times W$ 的云层，其左上角位于某个格子的正上方，且云层边平行于表格的坐标轴。随后会下雨，所有被这个云层覆盖到的部落都会得到水。

一个部落不需要完全位于云层下方；只要该部落中至少有一个格子位于云层下方，它就会获得供水。

请你求出：最多能让多少个部落获得供水。

输入格式

第一行输入四个整数 $N, M, H, W$，表示表格的大小以及云层的大小。

接下来 $N$ 行，每行输入 $M$ 个字符，字符之间以一个空格分隔。每个字符描述一个格子：

• 'x'（小写字母 x）表示该格中有人；
• '.' 表示该格为空。

输出格式

输出一行一个整数，表示问题的答案。

数据范围

• $1 \le N, M \le 3000$
• $1 \le W \le N$
• $1 \le H \le M$

子任务与评分

要获得某个子任务的分数，你的程序必须通过该子任务中的所有测试。

样例

输入

10 12 4 5
. x x . . x . . x x x .
. x . . x x . . . x x x
x x x . . x x x x . . .
. . x x . . . . . . x x
x . . x x x x . . . x x
x x . x . . x x . x x .
. x . . x x . x x . x .
. . x . . x x . . x x .
x x x . . . x x x x . .
. x . . x x . . . x . x

输出

4

样例说明

一个可行的云层放置方式是：令其左上角位于第 5 行第 1 列对应格子的上方。