← 返回题目
题库练习 order
← 上一题 下一题 →

A2548 | order

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $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
C++ 编辑器
输入
输出