Description

A “letter T” consists of one horizontal stroke and one vertical stroke, and the vertical stroke must be below the horizontal stroke (you may use the English letter T to help understand).

In this problem, we define the “horizontal stroke” as the horizontal line segment forming the “letter T”, and the “vertical stroke” as the vertical line segment forming the “letter T”.

Note that the overlapping part of the horizontal and vertical strokes is counted in both the horizontal length and the vertical length.

For a valid “letter T”, the length of the horizontal stroke must be odd, and the vertical stroke must intersect the horizontal stroke at its midpoint. The minimum horizontal length is $3$, and the minimum vertical length is $2$.

For example:

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

There is only one valid “letter T” (the red part).

Now you are given a $n \times m$ $01$ matrix. Please find, among all valid “letter T”s in this matrix, how many “letter T”s satisfy the following conditions.

Suppose a valid “letter T” has horizontal length $w$ and vertical length $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 horizontal length, vertical length, or the coordinates of the top-left corner are different.

Input Format

The first line contains two integers $n,m$, meaning the given $01$ matrix has $n$ rows and $m$ columns.

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

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

Output Format

Output one integer, the number of valid “letter T”s that satisfy the conditions.

5 5
3 3 18 9
11111
01110
11111
01110
11111

2

5 5
3 3 15 7
11111
01110
11111
01110
11111

7

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

8

Hint

[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\\\\ The\ 1st\qquad The\ 2nd \end{array}$$

Other than the two “letter T”s above, there are no other valid “letter T”s that satisfy the conditions, so the output is $2$.

[Constraints]
| Test Point ID | $n,m\le$ | $a,b\le$ | $s\le$ | $x\le$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1 \sim 4$ | $100$ | $100$ |$10^4$|$200$| | $5 \sim 8$ | $500$ | $500$ |$2.5\times 10^5$|$10^4$| | $9,10$ | $3\times 10^3$ | $0$ |$0$|$0$| | $11\sim 13$ | $3\times 10^3$ |$3\times 10^3$|$0$|$6\times 10^3$| | $14\sim 16$ | $3\times 10^3$ |$3\times 10^3$|$9\times 10^6$|$0$| | $17\sim 20$ | $3\times 10^3$ |$3\times 10^3$|$9\times 10^6$|$6\times 10^3$|

For $100\%$ of the testdata, $1 \le n,m \le 3\times 10^3$, $0 \le a,b \le 3\times10^3$, $0 \le s \le 9\times10^6$, $\space0 \le x \le 6\times10^3$.

Translated by ChatGPT 5