Problem Background

Given a $01$ matrix, we want you to find the "Letter T" composed of consecutive $1$s.

Problem Description

A "Letter T" consists of a horizontal line and a vertical line, with the vertical line always below the horizontal line (you can refer to the English letter T for better understanding).

In this problem, we define the "horizontal line" as the horizontal segment that forms the "Letter T," and the "vertical line" as the vertical segment that forms the "Letter T."

Note that the common part of the "horizontal line" and the "vertical line" is counted in both the length of the horizontal and vertical lines.

A valid "Letter T" must have an odd length for the "horizontal line" and the "vertical line" intersecting at the midpoint of the "horizontal line." The minimum length for the "horizontal line" is $3$, and the minimum length for the "vertical line" is $2$.

For example:

$$ \begin{array}{ccc} 0\color{Red}111\color{black}1\\ 00\color{Red}1\color{black}01 \end{array} $$

Contains only one valid "Letter T" (marked in red).

Now, given an $n \times m$ $01$ matrix, please find out how many valid "Letter T"s in the matrix satisfy the following conditions.

Let the length of the "horizontal line" of a valid "Letter T" be $w$, and the length of the "vertical line" be $h$, then:

• $w \ge a$
• $h \ge b$
• $w \times h \ge s$
• $w + h \ge x$

Two "Letter T"s are considered different if their lengths of the "horizontal line" or lengths of the "vertical line" or coordinates of the top-left corner are different.

Input Format

The first line contains two integers $n, m$, representing the number of rows and columns of the given $01$ matrix.

The second line contains four integers $a, b, s, x$.

The next $n$ lines, each containing $m$ numbers, which can only be $0$ or $1$, represent the given matrix.

Output Format

Output a single integer, representing the number of valid "Letter T"s that satisfy the conditions.

Sample Input and Output

Sample Input #1

5 5
3 3 18 9
11111
01110
11111
01110
11111

Sample Output #1

2

Sample Input #2

5 5
3 3 15 7
11111
01110
11111
01110
11111

Sample Output #2

7

Sample Input #3

10 10
5 4 40 11
0011111111
1011110101
1111111111
1001111101
1111101111
1111110110
0111011101
0111111110
0011111111
0111111101

Sample Output #3

8

Notes

[Sample Explanation #1]

$$ \begin{array}{ccc} \color{Red}11111\qquad11111\\01\color{Red}1\color{black}10\qquad01\color{Red}1\color{black}10\\ 11\color{Red}1\color{black}11\qquad11\color{Red}1\color{black}11\\ 01\color{Red}1\color{black}10\qquad01\color{Red}1\color{black}10\\ 11111\qquad11\color{Red}1\color{black}11\\\\ First\qquadSecond \end{array} $$

Apart from the above two "Letter T"s, there are no other valid "Letter T"s that satisfy the conditions, so the output is $2$.

[Data Range]

For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 3 \times 10^3$, $0 \le a, b \le 3 \times 10^3$, $0 \le s \le 9 \times 10^6$, $0 \le x \le 6 \times 10^3$.

见题面 Input 部分

见题面 Output 部分