You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

给你一个 $01$ 矩阵，我们希望你从中找到由连续的 $1$ 组成的「字母 T」。

题目描述

「字母 T」由一横和一竖组成，竖一定在横的下方（您可以借助英文字母 T 辅助理解）。

在本题中，我们定义「横」为组成「字母 T」的水平线段，「竖」为组成「字母 T」的竖直线段。

注意「横」与「竖」的公共部分同时计入横长和竖长。

合法的「字母 T」的「横」长必须为奇数且「竖」与「横」交于「横」的中点，「横」长最小为 $3$ ，「竖」长最小为 $2$。

如：

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

只含有一个合法的「字母 T」（即标红部分）。

现在给你一个 $n \times m$ 的 $01$ 矩阵，请你求出在这个矩阵中合法的「字母 T」中，一共有多少个满足以下条件的「字母 T」。

设某个合法的「字母 T」的「横」长为 $w$，「竖」长为 $h$，有：

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

两个「字母 T」不相同即两个「字母 T」的 「横」长 或 「竖」长 或 最左上角的坐标 不同。

输入格式

第一行，两个整数 $n,m$，表示给定的 $01$ 矩阵共有 $n$ 行 $m$ 列。

第二行，四个整数 $a,b,s,x$。

接下来 $n$ 行，每行 $m$ 个数，只可能是 $0$ / $1$，为给定的矩阵。

输出格式

输出一个整数，表示有多少个满足条件且合法的「字母 T」。

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

提示

【样例解释 #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\\\\ 第\ 1\ 个\qquad第\ 2\ 个 \end{array} $$

除了以上两个「字母 T」，没有其他满足条件且合法的「字母 T」，故输出 $2$。

【数据范围】

测试点编号	$n,m\le$	$a,b\le$	$s\le$	$x\le$
$1 \sim 4$	$100$		$10^4$	$200$
$5 \sim 8$	$500$		$2.5\times 10^5$	$10^4$
$9,10$	$3\times 10^3$	$0$	$0$	$0$
$11\sim 13$		$3\times 10^3$		$6\times 10^3$
$14\sim 16$			$9\times 10^6$	$0$
$17\sim 20$				$6\times 10^3$

对于 $100\%$ 的数据，满足 $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$。