Dead Or Alive

Time Limit: 10000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3185
64-bit integer IO format: %I64d      Java class name: Main

Description

Only several people survive after Doomsday, and a small number of cities have not been destroyed. yifenfei wants to arrange these people to live on the available cities.
Now all the people follow yifenfei to pass the cities.
But there are some restrictions on the cities. Some people will die when pass some cities and every city has a population limitation. If people can’t find a city to live after passing all cities they will be dead! So the order of passing the cities is important.

Input

The first line an integer T (1<=T<=100) which means the number of test cases.
Each case starts with two integers n and m, which means the number of people and the number of cities. (1<= n <= 31, 1 <= m <= 10)
Second line has m integers, the ith integer Ci means ith city’s population limitation. The cities are ordered from 0 to m-1. (1 <= Ci <= 6)
Then n lines follow. Each line starts with an integer k which means the number of cities this people will die when passing it. Then k integers follow.

Output

The maximum number of people can survive!

Sample Input

2
3 3
3 3 2
1 1
0
2 1 2
3 3
2 1 2
2 0 1
2 0 2
1 2

Sample Output

3
2

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .