Datta, the great politician, loves parties. He takes all the big shots with him to the most famous restaurant of Khulna City, the Hotel Royal. Datta thinks that feasting with the influential people will make him even more famous.
But there are problems handling important people. When they go to a restaurant, they only eat the food they like. Besides, if they do not find even a single dish that they want, they refuses to eat at all. Taking powerful people to restaurants and leaving them hungry looks very odd on Datta's part. That is why, he has hired you.
You will be given the type and the amount of dishes that Hotel Royal produces. You will also have the orders that Datta's dominant friends will make. You have to determine how Datta will maximize the number of stuffed guests.
The first line contains two integers n ( 1 ≤ n ≤ 15 ) and m ( 1 ≤ m ≤ 100 ), the number of guests Datta has and the types of dishes Hotel Royal produces. The next n lines describe the orders that his guests are going to make. Each line will be in the following format:
Oi a1 b1 a2 b2 ... an bn
Here, Oi ( 1 ≤ Oi ≤ 100 ) is the number of different items that person i is going to order. Each (aj,bj) pair describe one dish, where aj ( 1 ≤ ai ≤ m ) is the dish number and bj ( 1 ≤ bi ≤ 109 ) is the amount of ajth dish that the ith person is going to order. A person may order the same dish more than once.
The following m lines will contain one integer Mi ( 1 ≤ M ≤ 109 ), describing the amount of dish available of the ith type.
For each input, output one line: the maximum amount of people that Datta is going to satisfy. A person will be satisfied if all of his ordered dishes are presented to him.
| Input | Output |
|---|---|
1 1 1 1 100 100 | 1 |