## Scarecrow

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Burak, who is a farmer, is complaining that some parts of his field are fertile while others are quite inefficient. Burak seeks help from his friend Yiğit, an Agricultural Engineer to solve this problem. Yiğit does the soil test of Burak's field and gives the result to Burak. As a result of the test, Burak sees that some parts of his field are cultivable, and some other parts are uncultivable.

Burak's field $$\mathbf{N} \times \mathbf {M}$$ whose vertical length N is the horizontal length M is divided by 1x1 squares of equal dimensions. According to the test, areas marked with "#" cannot be cultivated, and areas marked with "." can be cultivated.

To protect his field, Burak wants to put a scarecrow that can protect an area of ​​height $$\mathbf{Y}$$ and width $$\mathbf{X}$$. While doing this, he wants the scarecrow to protect the maximum amount of cultivable land.

Note that Burak can place his scarecrow so that it protects any area of $$\mathbf{Y \times X}$$ on the farm. Can you help Burak in this matter?

#### Input

The first line contains the integers $$\mathbf{N}$$, $$\mathbf{M}$$, $$\mathbf{Y}$$, and $$\mathbf{X}$$. These integers show the vertical length of the field (the number of rows), the horizontal length of the field (the number of columns), the length and width of the area affected by the scarecrow, respectively.

After the first line, there is a $$\mathbf{N} \times \mathbf{M}$$ grid. This grid represents the field. The "#" characters in the grid represent areas that cannot be cultivable, and the characters "." represent areas that can be cultivable.

• $$1 \leq \mathbf{Y} \leq \mathbf{N} \leq 1000$$
• $$1 \leq \mathbf{X} \leq \mathbf{M} \leq 1000$$

#### Output

Print the maximum amount of cultivable 1x1 areas that the scarecrow can protect in one line.

#### Examples

Input 1:

3 8 2 2
#..##..#
.#.#.###
#..#...#

Output 1:

3

Input 2:

10 8 6 6
#..##..#
...#...#
#..#...#
....#..#
#..#...#
#..###.#
#..#.###
#..#...#
#..###.#
#..#.#.#

Output 2:

27

#### Explanation

Input-1:

Suppose the scarecrow is placed at the (1,1) position. In this case, the scarecrow can protect a single area.

• Suppose the scarecrow protects the rectangle (1,1)-(2,2). The cultivable area is 2.

Now, suppose the scarecrow is placed at the (1,2) position. In this case, the scarecrow can protect two different areas.

• Suppose the scarecrow protects the rectangle (1,1)-(2,2). The cultivable area is 2.

• Suppose the scarecrow protects the rectangle (1,2)-(2,3). The cultivable area is 3.

Now, suppose the scarecrow is placed at the (2,5) position. In this case, the scarecrow can protect four different areas.

• Suppose the scarecrow protects the rectangle (1,4)-(2,5). The cultivable area is 1.

• Suppose the scarecrow protects the rectangle (1,5)-(2,6). The cultivable area is 2.

• Suppose the scarecrow protects the rectangle (2,4)-(3,5). The cultivable area is 2.

• Suppose the scarecrow protects the rectangle (2,5)-(3,6). The cultivable area is 3.

In the end, the maximum cultivable area will be 3 for Input-1.