说明

$k$ 个朋友进入一间教室。已知每个朋友的身高 $h_i$，也已知教室内其他所有学生的身高。

教室可以表示为一个 $n \times m$ 的网格 $a$，每个单元格对应一个座位。第 $i$ 行第 $j$ 列的座位记作 $a_{i,j}$。对于每个座位，我们知道它是否已被学生占据（以及占据者的身高），或者为空座。

这 $k$ 个朋友想要在教室内就坐。每个朋友占据恰好一个空座，且不能有两个朋友坐在同一个座位上。此外，他们希望坐在同一行的连续座位上。更精确地说，他们选择一个行号 $i$（$1 \le i \le n$）和一个列号 $j$（$1 \le j \le m - k + 1$），然后坐在座位 $a_{i,j}, a_{i,j+1}, \dots, a_{i,j+k-1}$ 上。朋友们可以以任意顺序就坐；他们不必按照给定的身高顺序就坐。

一个朋友认为某个座位合适，仅当所有坐在他们前面（即同一列中行号较小的座位）的学生都比他们矮，确保他们有清晰的视线。一组朋友认为某个包含 $k$ 个连续座位的集合合适，当且仅当这组朋友可以安排自己，使得每个人都能获得清晰的视线。

综合考虑这些条件，教室内有多少组适合这群朋友的连续座位集合？

输入格式

第一行包含三个自然数 $n$、$m$ 和 $k$（$1 \le n, m \le 2000, 1 \le k \le m$），分别表示教室的行数、列数以及朋友的数量。

第二行包含 $k$ 个自然数 $h_1, h_2, \dots, h_k$，表示朋友的身高。

接下来的 $n$ 行，每行包含 $m$ 个自然数：如果 $a_{i,j} = 0$，则该座位为空；如果 $a_{i,j} \ge 1$，则该座位已被一个身高为 $a_{i,j}$ 的学生占据（$1 \le a_{i,j} \le 10^9$）。

输出格式

输出一行一个整数，表示在同一行中连续的 $k$ 个座位的集合数量，使得这些朋友可以安排就坐后每个人都能获得清晰的视线。

3 4 2
2 6
0 0 3 1
8 0 0 0
0 0 1 0

3

2 4 4
5 2 4 3
1 2 3 4
0 0 0 0

1

5 5 3
17 3 17
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

15

提示

第一个样例的解释：
两位朋友可以坐在第一行的第一和第二个座位、第二行的第二和第三个座位，或者第二行的第三和第四个座位。因此，他们可以坐在总共 $3$ 组不同的座位集合中。

第二个样例的解释：
四位朋友可以坐在仅有的四个空位上，只要他们按身高从矮到高排列。

第三个样例的解释：
由于教室内没有其他学生，三位朋友可以坐在同一行的任意三个连续座位上，因此共有 $15$ 种合适的座位安排。

计分方式

翻译由 DeepSeek V3.2 完成