Having now finalized which ski resort to stay at, it's time for Daniel to invite his friends! However, as it is winter, Daniel is unsure if all of his friends can make the drive to the resort. Thus, he will first make some calculations before asking around to see who is interested.
The location of the resort relative to each of his friends can be modelled by an -by- kilometre grid, with each friend located somewhere in the grid (possibly in the same square as another friend) and the ski resort itself located in the bottom-right corner. In addition, each square kilometre of land has a snow-elevation height, and thus it is only possible to drive into adjacent squares if the absolute difference in snow-elevation is less than or equal to .
Can you help Daniel determine how many of his friends can make the drive?
Constraints
Snow-elevation heights are integer values between and .
Subtask 1 [40%]
Subtask 2 [60%]
Input Specification
The first line of input will contain , , and .
The next lines each contain two integers, and , indicating a friend in the -th row and -th column of the grid.
The last lines will each contain integers, the snow-elevation height of every square in the row.
Output Specification
Output one integer, the number of friends that can make the drive to the resort.
Sample Input 1
2 4 3
1 1
2 4
1 8 3 3
5 2 3 4
4 4 4 9
6 2 4 6
Sample Output 1
1
Sample 1 Explanation
The first friend is trapped in their starting position! They cannot drive outside of cell . The second friend can go left, then down two squares, then right to reach the resort.
Sample Input 2
5 5 10
1 3
1 4
2 2
3 5
4 1
8 2 4 5 3
3 5 5 8 8
9 2 3 4 5
5 2 4 5 3
5 2 3 7 100
Sample Output 2
0
Comments