Skip to content

1203: 卖猪

题目

题目描述

你有$m$个猪圈,每个猪圈中有若干头猪。 有$n$个顾客按顺序来买猪,每个顾客需要若干头猪。 每个顾客都有某几个猪圈的钥匙(只有顾客才拥有钥匙),只有某个猪圈打开后才能分配这个猪圈里的猪,且顾客离开后会把门关闭。
每次你可以决定卖给每个顾客哪些猪(不能多于顾客需要的数量),并且可以在一个顾客买完后,调整没有锁门的猪圈中猪数量,比如,把几个猪圈中的猪全部转到一个猪圈内,请问最后最多能卖掉几头猪。

输入格式

输入的第一行是两个整数$m$和$n$。 其中$m$是猪圈的数量,$n$是顾客的数量。
输入的第二行有$m$个整数,表示每个猪圈里分别有多少只猪。
接下来$n$行,每行对应一个顾客的信息,格式如下。
第一个整数$a$表示该顾客拥有多少把钥匙。
接下来$a$个整数表示这些钥匙分别对应哪一些猪圈。
最后一个整数$b$表示该顾客想买多少头猪。

输出格式

输出一个整数表示最多可以卖出多少头猪。

样例输入

text 3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6

样例输出

text 7

数据范围

对于 100\%的数据,保证 $1\leq m \leq 1000, 1 \leq n \leq 100$,每个猪圈里猪的数量不超过$1000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!