Problem H
Remaking Orders

A delicious bowl of food Source: Pexels

You work in a very busy dining hall making food bowls that can have many different ingredients. When an order comes in, you read the list of ingredients to add to the bowl, add them one by one, and move on to the next order. However, every once in a while, you add the wrong ingredient to a bowl by mistake. Since you want to make sure that everyone gets their order correctly, you put the bowl aside and make a new one.

Sometimes, you realize that one of the next customers just so happens to want all of the ingredients that you had added to the bowl you set aside. In those cases, you can take that bowl again, add any other ingredients that may be missing, and serve it. For this reason, when you screw up an order, you always hold on to that bowl and try to use it later on.

After a while, the bowl will get cold, so if you haven’t managed to reuse it, you have to throw it away. You know that the bowl will be too cold to use if you have made a certain amount of bowls after setting it aside and you still haven’t used it. However, when you reuse a bowl that you had set aside and add new ingredients to it, the new ingredients will heat it up again and should you later make a mistake, you can keep the bowl for the same number of orders as when you added ingredients to it the first time.

On your counter, you only have space for two bowls: the one you’re making right now and at most one that you set aside. For this reason, when you screw up a bowl and you already have a bowl set aside, you have to throw the old one away and keep the new one on the counter. At the end of the day you must throw out any unfinished bowl.

You are curious about how many bowls you throw away each day, and you want to write a program to find out. However, all you have is the list of orders and a log of each time you added an ingredient to a bowl.

Input

Input begins with a line containing $3$ integers, $m$, $n$ and $c$. $m$ ($1 \leq m \leq 1\, 000$) is the number of ingredients available to order, which are numbered from $1$ to $m$. $n$ ($1 \leq n \leq 1\, 000$) is the number of orders received that day. $c$ ($0 \leq c \leq 1\, 000\, 000$) indicates how many complete bowls you can make after you last set aside away a bowl before it gets cold. For example, if $c=2$, you can make $2$ bowls without using the one you set aside, but if you don’t use it on the third bowl, it will get cold and will have to be thrown away. If you start using it on an order and then screw up, you can set it aside and make another $2$ bowls.

The following $n$ lines contain all the orders for that day. Each line begins with an integer $i$ ($1 \leq i \leq m$), the number of ingredients in the order. This is followed by a list of ingredients in the order, separated by spaces. All ingredients will be numbers in the range from $1$ to $m$ and will be distinct.

The final line of input contains the log of added ingredients, in order of when they were added. The line begins with an integer $k$ ($1 \leq k \leq 1\, 000\, 000$) representing the number of ingredients to follow. This is followed by $k$ integers separated by spaces, each representing an ingredient. Note that there will never be a situation in which you’re being asked to add an ingredient that is already in the bowl you are filling.

Output

Output a single integer, the number of bowls that were thrown away at the end of the day.

2 1 3
1 2
2 1 2

1

5 3 3
2 1 3
2 2 4
5 1 2 3 4 5
9 5 3 1 2 4 1 2 3 4

0