提示: 欢迎访问OurACM平台。
Problem 1980 AbOr's story

Accept: 255    Submit: 871
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

As we all known, AbOr has a lots of girls in a palace called “Hou” (About 30 millions).

The girls in the palace love gemstones, such as cat’s eye, garnet, amethyst and so on. If AbOr wants to play with one girl, he must take all the gemstones the girl wants. But the girl would not take any gemstones away. Though the gemstone is expensive, but AbOr is a businessman and he has infinity money. If AbOr plays with one girl, he will feel happy and she will help AbOr to make some money. AbOr likes the new and loathes the old, so if he plays with one girl he used to play with, he will not feel happy any more, of course make no money. Initially AbOr has no gemstones.

The evil AbOr want to make as much money as possible. But he is very busy, so your task is to help him to calculate the maximum money he can make.

Input

In the first line there is an integer T (T≤10), indicating the number of cases. Each case begins with a line containing two integers N and M (1≤N, M≤10,000), the number of the girls in the palace and the number of the kinds of gemstones AbOr can get. The following N lines, each line contains an integer Li (0≤Li≤M, 1≤i≤N) first, the number of the kinds of gemstones the i-th girl wants. We guarantee that the sum of Li (1≤i≤N) is no more than 100,000. Then following Li integers Gj (1≤Gj≤M, 1≤j≤Li), the index of the gemstone the i-th girl wants. We guarantee that no replication index of the gemstone will appear in these Li integers. Then following an integer P (1≤P≤1,000,000,000), the money AbOr could make after playing with the i-th girl. The next line contains M integers Sk (1≤Sk≤1,000,000,000, 1≤k≤M), the price of the k-th gemstone is Sk. The index of the gemstone is labeled from 1 to M.

Output

For each test case, print a line containing the test case number (beginning with 1) and the maximum money AbOr can make.

Sample Input

3 1 2 2 1 2 100 3 7 1 2 1 1 100 1000 10000 2 1 1 1 100 1 1 16 17

Sample Output

Case 1: 90 Case 2: 0 Case 3: 99

Source

The 35th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

Submit  Back  Status  Discuss