开始: 2024-06-23 14:30:00

20240623

结束: 2024-06-23 17:30:00
当前: 2025-0505-3030 10:49:45  类型:单人排位赛 状态:已经结束 
P4 : 藏宝图  
描述

有一天,超能侠获得了一张神秘的藏宝图。藏宝图可以视作一个大小为(L+1)*(L+1)的01矩阵A,左下角坐标为(0,0),右上角坐标为(L,L)。图上标出了n个点位,用1来表示。传说,冒险家的宝藏就埋在n个点位之一的地下。也就是说,矩阵中有且仅有n个1,展示出了宝藏的n个可能位置。

超能侠决定出发寻找宝藏,但n个位置一个一个找起来需要很长时间,于是他请占星术士帮忙,进一步缩小了宝藏可能的位置。具体而言,占星术士帮助他找出了藏宝图中的一小块,即从藏宝图中得到了一个大小为(S+1)*(S+1)的01矩阵B,称为“预言图”。预言图的左下角B[0][0]一定为1,标识了宝藏埋藏的位置。

但占星术士能力有限,该预言图可能与藏宝图中的多个位置相匹配,即对B上的任意一处坐标(i,j),都有多个A中的(x,y)满足A[x+i][y+i]=B[i][j]。请你结合藏宝图和预言图,判断有多少处位置满足条件。

输入

输入文件第一行给出三个整数n,L和S,分别表示点位数,藏宝图的大小,预言图的大小。

接下来n行,每行两个整数x和y,表示藏宝图中点位的坐标。

接下来S+1行输入完整的预言图,其中第i行包含S+1个0和1。注意最先输入的是B[S][0]...B[S][S]这一行。

输出

输出文件只有一行一个整数,表示藏宝图中有多少处可以与预言图对应,即可能埋藏着宝藏。

样例

输入

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

输出

3

输入

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

输出

0
提示

【输入输出样例1说明】

藏宝图中的(0,0),(1,1),(2,2)三处均可能埋有宝藏。

【输入输出样例2说明】

找不到对应的位置,如果将预言图左下角与藏宝图中的(3,3)处对应,则预言图右上角会超出藏宝图边界,对应不成功。

 

对于40%的数据,2≤L≤50;

对于100%的数据,2≤n≤1000,2≤L≤2000,1≤S≤50,始终保证S<L,n≤(L+1)*(L+1)。

(思考:若L≤10^9,应该如何处理?)