#P1391. [CEOI2008]order

    ID: 403 传统题 10000ms 512MiB 尝试: 2572 已通过: 492 难度: 6 上传者: 标签>CF2000提高+/省选-最小割建模最大流最小割定理Dinic当前弧优化闭合子图问题

[CEOI2008]order

[CEOI2008] order

题目描述

有 NN 个工作,MM 种机器,每种机器可以租或者买。每个工作需要若干种不同的机器来完成。购买一种机器只需支付一次费用,之后可用于任意多个工作而无需额外费用;租赁费用针对具体工作分别支付。可以放弃任意工作,放弃后没有收入也无需支付其费用。

你需要最大化利益。

输入格式

第一行给出 N,MN,M。

接下来若干行描述一个工作,对于每个工作,第一行给定 xix_i 和 tit_i,分别表示此工作的收入和所需机器的种数,1≤ti≤M1\le t_i\le M。

后面 tit_i 行,每行两个整数 aija_{ij} 和 bijb_{ij},分别表示此工序需要的机器和此工作租用此机器的费用。

最后 MM 行,每行一个正整数表示购买机器的费用 yiy_i。

输出格式

最大利润

样例 #1

样例输入 #1

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

样例输出 #1

50

提示

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