Choosing Orders and Renting Machines

Carpenter Sam receives $N$ orders. To finish them she needs $M$ machines that she does not yet own. Not every order needs every machine, but each order needs at least one of them.

To complete an order, Sam must, for each machine that order requires, either buy that machine or rent it. The rent of a machine depends on the order it is used for, because different orders need different amounts of work on it. The purchase price of a machine does not depend on any order, and a machine that has been bought once can be used for any number of orders at no additional cost.

If an order would cost more than it earns, Sam may reject it; a rejected order brings neither income nor cost.

Order $i$ has income $v_i$. Completing it requires a given set of machines, and for each required machine $j$ the rent is $r_{ij}$. Machine $j$ has purchase price $s_j$.

Decide which orders to complete, which machines to buy, and which machines to rent so that Sam's profit (the total income of the completed orders minus every purchase and rent cost) is as large as possible. Because rejecting every order gives a profit of $0$, the answer is never negative.

The first line contains two integers $N$ and $M$ ($1 \le N \le 1200$, $1 \le M \le 1200$).

Then follow $N$ order blocks. The block for order $i$ begins with a line holding two integers: the income $v_i$ ($1 \le v_i \le 5000$) and the number of required machines $m_i$ ($1 \le m_i \le M$). Each of the next $m_i$ lines contains two integers $j$ and $r_{ij}$ ($1 \le j \le M$, $1 \le r_{ij} \le 20000$): a machine required by order $i$ and the rent to use that machine for this order.

After the last order block come $M$ lines; the $j$-th of them contains one integer $s_j$ ($1 \le s_j \le 20000$), the purchase price of machine $j$.

Print one integer: the maximum achievable profit.

In the first sample a maximum profit of $50$ can be reached in two different ways:

• Reject order $2$, complete order $1$, and rent both machine $1$ and machine $2$.
• Complete both orders, buy machine $1$, and rent machine $2$ and machine $3$.

Either choice yields a profit of $50$.