Fast Food Prizes

Interview

Time limit2sMemory limit128 MB

Summary

Add up, over disjoint prize sets, the prize value times the smallest sticker count among its required kinds.

Level: Easy2 of 10
Topics: Greedy, Math, Array
Solved: No attempts yet

Problem

While a regional programming contest runs in Daejeon, the fast food restaurants in the city hold a promotion. Every featured item you eat comes with one sticker, and stickers can be traded for prize money.

Each prize lists the sticker kinds it needs. Handing in one sticker of every kind on that list wins the prize, and the same prize can be claimed again while the stickers last. At most one prize asks for a given kind of sticker, so two different prizes never need the same kind. Some stickers are not needed for any prize.

On the way to the contest your coach allowed meals only at fast food restaurants. What is the largest total prize money the stickers the coach collected can be traded for?

Input

The first line contains the number of test cases.

The first line of each test case contains the number of prizes n (1 ≤ n ≤ 10) and the number of sticker kinds m (1 ≤ m ≤ 30). The kinds are numbered 1 through m.

Each of the next n lines describes one prize. A line contains the number of sticker kinds the prize needs, k (1 ≤ k ≤ m), then those k kind numbers, then the amount of the prize. The amount is at most 1,000,000.

The last line of the test case contains how many stickers of kind 1 through kind m the coach has, in that order. Each count is at most 100.

Output

For each test case, print the largest total prize money on its own line.

Examples3

Example 1

Input

3
2 10
3 1 2 3 100
4 4 5 6 7 200
2 3 1 4 5 2 2 1 3 4
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 3 4 5 6
3 6
2 1 2 100
3 3 4 5 200
1 6 300
1 2 0 4 5 6

Expected output

500
2500
1900

Example 2
Input
```
1
1 3
2 1 2 500
7 4 9
```
Expected output
```
2000
```

Example 3

Input

Expected output