[CEOI2008]order

题目描述

有 $N$ 个工作,$M$ 种机器,每种机器可以租或者买。每个工作包括若干道工序,每道工序需要某种机器来完成。 你需要最大化利益。

输入输出格式

输入格式


第一行给出 $N,M$。 接下来若干行描述一个工作,对于每个工作,第一行给定 $x_i$ 和 $t_i$,分别表示此工作的收入和工序数。 后面 $t_i$ 行,每行两个整数 $a_{ij}$ 和 $b_{ij}$,分别表示此工序需要的机器和此工作租用此机器的费用。 最后 $M$ 行,每行一个正整数表示购买机器的费用 $y_i$。

输出格式


最大利润

输入输出样例

输入样例 #1

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

输出样例 #1

50

说明

对于 $100\%$ 的数据满足 $1\le N,M\le 1200,1\le x_i\le 5000,b_{ij},y_i\le 20000$。