Description

Xiao B has $N$ subordinates. Now Xiao B plans to bring some subordinates to have photos taken.

There are $M$ people; each person is willing to pay Xiao B some money to take a photo with some of the $N$ subordinates. If that set of subordinates is not fully brought, the photo cannot be taken, and Xiao B will not receive the payment.

Note: Bringing subordinates is not free! For each subordinate who is brought, Xiao B needs to pay a fee to ensure cooperation during the photo.

Input Format

The first line contains $2$ positive integers $M$ and $N\ (1\leq M, N\le 100)$. The next $M$ lines each describe one requester’s data. The first number is the fee he agrees to pay for that photo; then follow the IDs of the required subordinates, terminated by a $0$ as the end marker for the line. The last line contains $N$ numbers, the cost to bring each subordinate.

Output Format

A single number, the maximum profit. Xiao B may choose to bring nobody.

2 3
10 1 2 0
25 2 3 0
5 6 7

17

Hint

For $10\%$ of the testdata, each person requires all $N$ subordinates.

For $30\%$ of the testdata, $N, M\le 15$.

For another $10\%$ of the testdata, the answer is $0$.

For $50\%$ of the testdata, $N, M\le 40$.

For another $10\%$ of the testdata, each person requires exactly one subordinate.

For $100\%$ of the testdata, $1\leq N, M\le100$, and fees are integers in $[1, 5\times 10^8]$.

Translated by ChatGPT 5