K. Kitchen Closing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's a busy evening at Chef Elisa's restaurant, and the kitchen is working tirelessly to fulfill the orders of hungry clients. Elisa is known for her creativity, using a wide variety of fresh ingredients to craft her famous dishes. The kitchen is stocked with $$$N$$$ different ingredients, each available in limited quantities, and the staff has prepared a menu of $$$M$$$ signature dishes, each requiring specific ingredients to make.

A large crowd has gathered, and the kitchen is being flooded with orders, each containing requests for multiple dishes. Elisa is determined to fulfill the orders in the order they are received, but there's a catch: the kitchen only has so many ingredients, and they must be used carefully.

As the evening progresses, Elisa notices that the ingredients are running low. The kitchen staff must figure out how many consecutive orders they can fulfill, starting from the first, before they can no longer make the requested dishes due to a lack of ingredients. If the kitchen does not have enough ingredients to plate all the dishes from an order, then that order can not be fulfilled, once an order cannot be fulfilled, the kitchen will close for the night

Your task is to help Elisa and her staff determine how many orders can be processed in the order they arrive, before they run out of ingredients and are unable to fulfill the next order.

Input

The first line of input contains three integer numbers separated by a space $$$N$$$ ($$$1 \leq N \leq 100$$$), $$$M$$$ ($$$1 \leq M \leq 100$$$), and $$$O$$$ ($$$1 \leq O \leq 100$$$), representing the number of ingredients in the kitchen, the number of dishes in the menu, and the number of orders to be processed.

The second line contains $$$N$$$ integer number separated by a space, representing the quantity $$$q_i$$$ ($$$1 \leq q_i \leq 10000$$$) that the kitchen has available for the $$$i$$$-th ingredient.

$$$M$$$ descriptions of dishes follow. Each description starts with a line that contains an integer number $$$m_i$$$ ($$$1 \leq m_i \leq N$$$), representing the number of different ingredients required to serve dish $$$i$$$, followed by $$$m_i$$$ lines, each of these lines contains two integer numbers separated by a space $$$I_i$$$ ($$$1 \leq I_i \leq N$$$) and $$$q_{m_i}$$$ ($$$1 \leq q_{m_i} \leq q_{I_i}$$$), representing the $$$i-th$$$ ingredient and the quantity of the ingredient required to make that dish.

Each of the next $$$O$$$ lines describe an order, each order starts with an integer $$$o_i$$$ ($$$1 \leq o_i \leq 100$$$), representing the number of dishes in the order, followed by a list of $$$o_i$$$ integer numbers where each integer $$$d_i$$$ ($$$1 \leq d_i \leq M$$$) represents a dish in the order.

Output

Print a single integer number, the number of orders the kitchen can fulfill before closing.

Examples
Input
1 2 3
10
1
1 1
1
1 2
5 2 2 2 2 2
1 1
2 1 1
Output
1
Input
1 2 3
10
1
1 1
1
1 2
5 1 1 1 1 1
1 1
2 1 1
Output
3
Input
2 2 3
12 10
1
1 1
2
1 2
2 2
5 2 2 2 2 2
1 1
2 1 2
Output
2