Choosing Orders and Renting Machines

Carpenter Sam receives N orders. While reading the orders she realizes that
she is missing M machines necessary to complete the orders. Not all orders
require all missing machines, but every order requires at least one of them.
To complete an order, Sam needs to either buy or rent each of the machines
the order requires.

Since different orders need different amounts of work (and thus time) on
each machine, the rent for a machine may depend on the
order that is completed on it. The purchase
cost for a machine do not depend on the orders, though. A machine which is
purchased once can be used to work on any number of orders at no extra cost.
If the cost caused by an order seem too high to Sam, she may choose to
reject an order; this will lead to no cost (and no profit).
Help Sam decide which orders to reject, which machines to buy, and which
machines to rent in order to maximize her profit.

N = 2, M = 3
Order   | Sam’s Income if Completed
O1             100
O2             100
Machine | Purchase Price
M1             50
M2             80
M3            110
Order   |  Machine Required by Order  | Rent to Complete Order on Machine
O1             M1                                   30
               M2                                   20
O2             M1                                   40
               M3                                   80
There are two solutions leading to the maximum profit of 50:
• Reject O2, complete O1, rent both M1 and M2.
• Complete both O1 and O2, buy M1, rent M2 and M3.


PROBLEM NAME: order2

INPUT FORMAT:

* Line 1: Two integers, N (1 <= N <= 1,200) and M (1 <= M <= 1,200).

* Lines 2..end of input: The following N blocks of lines each describe
        an order; they are structured as follows: The first line of
        block i contains two integers, the income value vi (1 <= vi <=
        5 000) for order Oi and the number of machines mi (1 <= mi <=
        M) needed for Oi. The following mi lines each specify a
        machine j (1 <= j <= M) needed to complete Oi and the rent
        r_ij (1 <= r_ij <= 20 000) needed to rent this machine for
        this order. The M lines after the last order block contain one
        integer each: the purchase price si (1 <= si <= 20 000) for
        each machine.

SAMPLE INPUT:

2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110

OUTPUT FORMAT:

* Line 1: One integer, the maximum achievable profit.

SAMPLE OUTPUT:

50