A2548. order
编程题
省选/NOI-
知识点
题目描述
有 $N$ 个工作，$M$ 种机器，每种机器可以租或者买。每个工作包括若干道工序，每道工序需要某种机器来完成。
你需要最大化利益。
你需要最大化利益。
输入格式
第一行给出 $N,M$。
接下来若干行描述一个工作，对于每个工作，第一行给定 $x_i$ 和 $t_i$，分别表示此工作的收入和工序数。
后面 $t_i$ 行，每行两个整数 $a_{ij}$ 和 $b_{ij}$，分别表示此工序需要的机器和此工作租用此机器的费用。
最后 $M$ 行，每行一个正整数表示购买机器的费用 $y_i$。
接下来若干行描述一个工作，对于每个工作，第一行给定 $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$。