Background

Summer vacation is coming . Unfortunately for a variety of reasons , Small P The original travel plan was cancelled . Disappointed little P I can only stay on West Island for a slightly monotonous holiday …… until ……

One day , Small P Got a mysterious treasure map .

Problem description

On the island of sisieffer, there are  n  tree , The specific positions of these trees are recorded on a green map .
In short , The greening map of West Aifo island can be regarded as a map with a size of  (L+1)×(L+1)  Of  01  matrix  A,
The lower left corner of the map （ coordinate  (0,0)） And the upper right corner （ coordinate  (L,L)） They correspond to each other  A[0][0]  and  A[L][L].
among  A[i][j]=1  Representation coordinates  (i,j)  There is a tree planted there ,A[i][j]=0  The coordinate  (i,j)  There are no trees .
In other words , matrix  A  There are and only  n  individual  1  It shows the island of West Eiffer  n  The exact location of the tree .

Legend has it that , The great adventurer Dunton's treasure is buried under a tree .
also , Dunton also cut a small piece from the green map of West West iver island , Make a treasure map to indicate its location .
say concretely , The treasure map can be regarded as a treasure map with a size of  (S+1)×(S+1)  Of  01  matrix  B（S  Far less than  L）, Corresponding  A  Some part of .
Theoretically , Greening map  A  There is a coordinate in  (x,y)（0≤x,y≤L−S） And the treasure map  B  The lower left corner  (0,0)  Corresponding , The meet ：
Yes  B  Any coordinate on  (i,j)（0≤i,j≤S）, There are  A[x+i][y+j]=B[i][j].
When the above conditions are met , We think of the treasure map  B  Corresponding to the greening map  A  The lower left corner in the middle is  (x,y)、 The upper right corner is  (x+S,y+S)  Region .

actually , Considering that the treasure map depicts only a small area , Coordinates satisfying the above conditions  (x,y)  There may well be more than one .
Please refer to the greening map of West Eiffer island  n  The location of the tree , And small  P  The treasure map in your hand , Judge how many coordinates in the greening map meet the conditions .

Specially , The lower left corner of the treasure map must be a tree , namely  A[x][y]=B[0][0]=1, It shows where the treasure is buried .

Input format

Reading data from standard input .

The first line of input contains three positive integers separated by spaces  n、L  and  S, They represent the number of trees on the island of West Eiffer 、 The size of green map and treasure map .

Because the size of the greening map is too large , The input data contains only  n  The coordinates of a tree, not a complete map ; And then  n  Each row contains two integers separated by spaces  x  and  y, Represents the coordinates of a tree , Satisfy  0≤x,y≤L  And the same coordinate will not be repeated .

Last  (S+1)  Line input small P The complete treasure map in your hand , Among them the first  i  That's ok （0≤i≤S） Contains space delimited  (S+1)  individual  0  and  1, Express  B[S−i][0]⋯B[S−i][S].
We need to pay attention to , The first input is  B[S][0]⋯B[S][S]  a line ,B[0][0]⋯B[0][S]  Enter... At the end of a line .

Output format

Output to standard output .

Output an integer , Indicates how many coordinates in the green map can correspond to the lower left corner of the treasure map , That is to say, there may be buried treasures .

Examples 1 Input

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

Data

Examples 1 Output

3

Data

Examples 1 explain

On the green map  (0,0)、(1,1)  and  (2,2)  There may be treasures buried in all three places .

Examples 2 Input

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

Data

Examples 2 Output

0

Data

Examples 2 explain

If you compare the lower left corner of the treasure map with the greening map  (3,3)  Corresponding to , The upper right corner of the treasure map will exceed the boundary of the green map , The correspondence is not successful .

Train of thought

Use direct simulation , Design a huge map map1 Used to store all maps , Mark the tree in the map as 1. Traverse all the trees first , Compare the treasure map in each iteration , Check whether the conditions are met .

Code

n,L,S=map(int,input().split())
map1=[[0 for _ in range(L+1)] for _ in range(L+1)]

begin=[]
for i in range(n):
    x,y=map(int,input().split())
    begin.append((x,y))
    map1[x][y]=1


map2=[]
for i in range(S+1):
    map2.append([int(i) for i in input().split()])

map2.reverse()

cnt=0
for x,y in begin:
    flag=0
    for i in range(S+1):
        for j in range(S+1):
            if x+i>L or y+j>L:
                flag=1
            elif map1[x+i][y+j]==map2[i][j]:         
                continue
            else:
                flag=1
                break
        if flag==1:
            break
    if flag==1:
        continue
    else:
        cnt+=1

print(cnt)

defects

Because this method designs a huge matrix , If the data given in the topic is too large, it will cause memory overflow , Can only pass 70% The data of

Ideas 2

Ideas 2 Make improvements on idea one , Use a dictionary to store the largest map , This can effectively reduce the use of memory . Because of the change of storage mode , Therefore, the judgment conditions of our circular judgment should also be changed . The judgment condition of train of thought 1 is

            if x+i>L or y+j>L:
                flag=1
            elif map1[x+i][y+j]==map2[i][j]:         
                continue
            else:
                flag=1
                break

But we don't have map1 了 , To solve this problem , We should change it to this

            if x+i>L or y+j>L:
                flag=1
            if map2[i][j]:
                if (x+i,y+j) not in map1:
                    flag=1
                    break
            else :
                if (x+i,y+j) in map1:
                    flag=1
                    break

In this way, we can effectively judge whether the treasure map and the big map match .

Code

n,L,S=map(int,input().split())

# Design a dictionary for storing trees , Save enlarged map 
map1={}
begin=[]
for i in range(n):
    x,y=map(int,input().split())
    begin.append((x,y))
    map1[(x,y)]=1

# Treasure map 
map2=[]
for i in range(S+1):
    map2.append([int(i) for i in input().split()])

map2.reverse()

cnt=0
# Traverse all trees 
for x,y in begin:
    flag=0
    # Compare the treasure map 
    for i in range(S+1):
        for j in range(S+1):
            if x+i>L or y+j>L:
                flag=1
            if map2[i][j]:
                if (x+i,y+j) not in map1:
                    flag=1
                    break
            else :
                if (x+i,y+j) in map1:
                    flag=1
                    break
        if flag==1:
            break
    if flag==1:
        continue
    else:
        cnt+=1

print(cnt)