Technology Trader

Time Limit: 1 Second    Memory Limit: 32768 KB
Special Judge

Mr. Black is a merchant doing technology trading business. He gets orders from his customers and then he analyzes the requests, finding out all the components in need. He then turns to his suppliers to collect those components that he can integrate them to build his own tech-products for sale. Some components can be used for several products so Mr. Black buys them only once. His own products are also unique and sale for once, because his customer would not turn back to buy a same thing twice.

Each product has its own value, though. As well as Mr. Black makes money, so do his suppliers. Hence Mr. Black must choose the set of products he will produce to make out the maximum profit. He may discard some orders in case they can not contribute to his maximum profit.

Now the problem comes to you, his assistant, to find out which orders shall be accepted and what components hence shall be purchased to make out these products, that, Mr. Black can make his maximum profit from them.

Input

One integer specifying how many cases there are to be processed.

For each case:

One integer specifying the components Mr. Black has at his database, followed by that many lines, each specifying:


One integer specifying how many orders Mr. Black has received. followed by that many data blocks at the following format:
<'nComp' for components required for this product>

Then 'nComp' lines follows each specifying a component name this product requires.

There will be one blank line above each block and all names contain maximum 32 upper case alphabetic characters.

The number of components will not exceed 250 and there will be no more than 100 orders. All integers are at range [0, 10000].

Output

For each case the following output is required:

One integer telling the maximum profit Mr. Black can make out of his orders, with such details following:

One integer telling how many orders are chosen, followed by that many lines each stating the product names (any order).

One integer telling how many components shall be purchased, followed by that many lines each stating their names (any order).

If several plans have the same maximum profit, any one will be accepted.

Output one blank line between each two consecutive blocks.

Sample Input

1

4
ENGINE 8000
NAVIGATION 2000
GPS 1500
RADAR 1500
2
MISSILE 4000 3
ENGINE
NAVIGATION
GPS
AUTOPILOT 9000 2
GPS
RADAR

Sample Output

6000
1
AUTOPILOT
2
GPS
RADAR

Submit

Source: ZOJ Monthly, January 2004