
ZOJ Problem Set  3491
We are from the kingdom of decayeds, to help the human innovate, and get the suffer away, all we need is your brain!  by Zombies
Your garden is consisted of several lanes. The zombies are moving along the lanes in your garden. But as they are moving very slowly, you can assume they are still. The wallnuts are thrown out one after another. That is to say, a wallnut will not be thrown out until the previous one goes out of the garden. Each wallnut goes along the lane from left to right at first. After hitting the first zombie, it will go diagonally at 45 degree, in the direction which is farther from the edge. For example, if there are 4 lanes numbered from 1 to 4 from top to bottom, a wallnut from lane 3 will go upper right after hitting the first zombie, while the one from lane 2 or lane 1 will go bottom right. To simplify the case, you can assume that the number of lanes is always even so that you can determine the direction after the first hit. After that, the wallnut will reflect if it hits another zombie or hit the upper edge of bottom edge of the garden. That means a wallnut which goes upper right originally will go bottom right after the reflection and vice versa. Each zombie can be defeated by one hit of a wallnut. If there are several zombies standing at the same place, one hit can defeat only one of them. Given the place of each zombie and the lane each wallnut goes, you are asked to calculate the number of zombies that are defeated by the wallnuts. Input There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases. The first line of each test case contains 3 integers N, M and K, indicating the number of lanes, the number of zombies and the number of wallnuts (0 < N ≤ 2000, 0 < M ≤ 200000, 0 < K ≤ 100000). M lines follow, each of which contains 2 integers xi and yi(0 < xi ≤ 1000000, 1≤ yi ≤ N), describing the coordinates of the ith zombie. Then K lines follow, each of which contains 1 integer ci(1 ≤ ci ≤ N), the number of lane where the ith wallnut is put. Output Output the number of zombies that are defeated in one line. Sample Input 4 2 2 1 1 1 1 1 1 2 1 2 1 1 1 1 4 2 1 1 2 2 3 2 4 2 1 1 1 5 3 1 Sample Output 1 1 2 2 Hint In the last sample, the wallnut hit zombie at (1, 1) and then go through (2, 2), (3, 3), (4, 4), and hit the second zombie at (5, 3). Author: GUAN, Yao Contest: The 8th Zhejiang Provincial Collegiate Programming Contest 