P3410 Taking Photos

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.

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.

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

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