The Programmers is a popular reality show focusing on programming contest. Each year many people would enter the contest, and compete to be the next top programmer. Due to its popularity, several people would like to enter the show. The Programmers organizes local contests around Thailand to find the great talents. Each local contest site can only handle C contestants. However, due to exhausted problem setters, there are only S local-contest sites, numbered from 1 to S. Note that all local contests are organized at the same time. Hence, one contestant can only participate in at most one of the local contest. The local contest sites are located all over the country. For some contestants, it is not possible to go to the sites that are very far from their home town. To facilitate the contestants, the organizer asks each contestant to list local contest sites that they can join. Some contestant might not be able to compete because these constrains. Your task is to calculate the maximum overall number of contestants that can participate in the local contests without breaking these constrains. Input In the first line of input contains a single integer, n — the number of test cases. There are at most 20 test cases. This is followed by n test cases, each contains m + 1 lines using the following format. • The first line contains four integers: P, S, C, m. P is the number of people applying to the local contests, numbered from 1 to P. S is the number of sites. C is the number of contestants that each site can handle. (1 ≤ P ≤ 500; 1 ≤ S ≤ 20; 1 ≤ C ≤ 100) • The next m following lines describe the sites that each contestant can participate. Each line contains 2 integers, the index of the contestant and the index of the local site that that contestant can join. Output For each test case, print the number of maximum contestants that the Programmers can accommodate to all of its local contest sites. Sample Input 2 2214 11 12 21 22 4 3 1 12 11 12 13 21 22 23
2/2 31 32 33 41 42 43 Sample Output 2 3