Every year, the penguins gather for their traditional Penguin Festival. This year, Mumble is in charge of the whole event. However, instead of booking an ice shelf for the event, this year, Mumble decides to hold the Penguin Festival in the penguins' own backyard at Rafiki Island (RI).

Of course, the penguins weren't happy with it, but they didn't really understand Mumble. You see, Mumble is a very very nice penguin. He actually wants to use the money saved for a lucky draw. In fact, one lucky draw simply isn't enough for Mumble. He wants to hold many rounds of lucky draws!

This lucky draw is special in that the guests choose their own lucky numbers. However, Mumble isn't exactly a very rich penguin, and simply cannot afford to be giving out prizes for free. So, in order for him to be able to hold the multiple lucky draws at all, he needs to determine the lucky number to announce such that as few penguins as possible will win. Obviously, Mumble still wants his penguin friends to win prizes, so at least one penguin must win at each round.

Mumble surveys the penguins' lucky draw numbers at each round. Before each lucky draw at specific rounds during the party, he will ask the penguins for their chosen lucky numbers. Each time, some of them change their minds. Also, some penguins may have left the party or there might be newcomers to the party.

Help Mumble determine how many lucky draw prizes he needs to give out by the end of the party.

Input

The first line contains two integers, n (the number of guests in the party at the start) and i (the number of rounds).

The next n lines contain the guest number and their lucky draw number.

The next line contains c (the number of guests who changed their mind or left or join) followed by c lines, containing two integers: the guest number and their favourite number. If the number is 0, it means that they have left the party. If the guest number is was not reflected, he is a new guest.

This goes on for i - 1 lines (the start of the party is the first round of lucky draw).

Output

Output the total number of lucky draw prizes Mumble will have to give away.

Limits

For 20% of the test cases, 1 ≤ n ≤ 10, 1 ≤ i ≤ 10.

For 50% of the test cases, 1 ≤ n ≤ 100, 1 ≤ i ≤ 100.

For 100% of the test cases, 1 ≤ n ≤ 1000, 1 ≤ i ≤ 1000.

1 ≤ guest number < 10000, 1 ≤ lucky draw number < 10000.

Sample Input

5 3
1 2
2 2
3 2
4 5
5 10
3
6 10
4 0
7 2
1
1 1

Sample Output

4

Explanation

At the first round of lucky draw, Mumble can choose the number '5' or '10', giving out only one lucky draw prize.

At the second round of lucky draw, 2 new penguins, 6 and 7, joined the party, and penguin 4 left. This leaves 6 penguins with lucky draw numbers: 2, 2, 2, 10, 10, 2.

Mumble can now choose '10', giving out 2 lucky draw prizes this time.

At the third round of lucky draw, penguin 1 changed his mind. This leaves 6 penguins with lucky draw numbers: 1, 2, 2, 10, 10, 2.

Mumble can now choose '1', giving out 1 lucky draw prize this time.

After the party, Mumble gave out a total of 4 lucky draw prizes.