1 人解决，4 人已尝试。
1 份提交通过，共有 25 份提交。
9.9 EMB 奖励。
单点时限: 10.0 sec
内存限制: 256 MB
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.
Example
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 |
| O1 | M2 | 20 |
| O2 | M1 | 40 |
| O2 | M2 | 80 |
There are two solutions leading to the maximum profit of 50:
The first line of the input contains two integers, N (1 <= N <= 1 200) and M (1 <= M <= 1 200). 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 rij (1 <= rij <= 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.
The output contains exactly one integer: the maximum achievable profit.
2 3 100 2 1 30 2 20 100 2 1 40 3 80 50 80 110
50
1 人解决，4 人已尝试。
1 份提交通过，共有 25 份提交。
9.9 EMB 奖励。