[CEOI2008Day2] Choosing Orders and Renting Machines

内存限制：256 MB 时间限制：1000 ms

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 diﬀerent orders need diﬀerent 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 proﬁt). Help Sam decide which orders to reject, which machines to buy, and which machines to rent in order to maximize her proﬁt.

Example

$N = 2, M = 3$

There are two solutions leading to the maximum proﬁt of 50:

Reject $O_2$, complete $O_1$, rent both $M_1$ and $M_2$.
Complete both $O_1$ and $O_2$, buy $M_1$, rent $M_2$ and $M_3$.

The ﬁrst line of the input contains two integers, $N (1≤ N ≤1200)$ and $M (1≤ M ≤1200)$.

The following $N$ blocks of lines each describe an order; they are structured as follows: The ﬁrst line of block $i$ contains two integers, the income value $v_i (1 ≤ v_i ≤ 5000)$ for order $O_i$ and the number of machines $m_i (1 ≤ m_i ≤ M)$ needed for $O_i$. The following $m_i$ lines each specify a machine $j (1 ≤ j ≤ M)$ needed to complete $O_i$ and the rent $r_{ij} (1 ≤ r_{ij} ≤ 20000)$ needed to rent this machine for this order.

The $M$ lines after the last order block contain one integer each: the purchase price $s_i (1≤ s_i ≤ 20000)$ for each machine.

The output contains exactly one integer: the maximum achievable proﬁt.

样例输入 1

C0515 [CEOI2008Day2] Choosing Orders and Renting Machines

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示