光伏电站建设区域统计

题目描述

某电力公司计划在一片 $N \times M$ 的矩形区域内建设光伏电站。该区域已被划分为 $1 \times 1$ 的单位地块，并且公司对每一块土地都进行了年发电量评估。

电站的建设必须遵循以下规则：

1. 电站必须是边长为 $L$ 的正方形区域。
2. 正方形电站区域内，所有单位地块的总年发电量必须不低于一个给定的阈值 $P$。

现在，给定整个区域的发电量评估地图、正方形电站的边长 $L$ 以及最低总发电量要求 $P$，请你计算有多少个不同的位置可以建设符合要求的电站。

输入格式

第一行输入四个整数 $N, M, L, P$，分别表示调研区域的行数、列数，电站的正方形边长，以及最低总发电量要求。

接下来 $N$ 行，每行包含 $M$ 个整数，表示调研区域内每平方公里（单位地块）的年发电量。

输出格式

输出一个整数，表示可以建设符合要求的电站的区域总数。

样例

样例输入

2 5 2 6
1 3 4 5 8
2 3 6 7 1

样例输出

4

提示

样例说明

• 调研区域为 $2 \times 5$ 的网格，电站边长为 $L=2$，最低发电量要求 $P=6$。
• $2 \times 2$ 的正方形区域的左上角可能的位置有 $(1,1), (1,2), (1,3), (1,4)$。
• 我们来逐一检查这些区域的总发电量：
  • 左上角为 $(1,1)$ 的区域：包含 $\{1, 3, 2, 3\}$，总和为 $9 \ge 6$。符合要求。
  • 左上角为 $(1,2)$ 的区域：包含 $\{3, 4, 3, 6\}$，总和为 $16 \ge 6$。符合要求。
  • 左上角为 $(1,3)$ 的区域：包含 $\{4, 5, 6, 7\}$，总和为 $22 \ge 6$。符合要求。
  • 左上角为 $(1,4)$ 的区域：包含 $\{5, 8, 7, 1\}$，总和为 $21 \ge 6$。符合要求。
• 总共有 $4$ 个符合要求的建设区域。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N, M \le 1000$
• $1 \le L \le \min(N, M)$
• $0 \le P \le 10^9$