MPIGS - Sell Pigs
题意翻译
Mirko在一个养猪场工作，养猪场有M个关着的猪圈，Mirko不能打开任何猪圈，因为他没钥匙。顾客一个接一个地来到养猪场，他们各拥有一些猪圈的钥匙，想买若干猪。Mirko早就知道关于那天来农场顾客的所有数据，他可以制定一个销售计划，以便尽可能增加出售的猪的数量。更明确地，整个过程如下：顾客来啦，顾客用手里的钥匙打开猪圈啦，Mirko把他要的猪(从所有打开着的猪圈)卖给他啦，(如果Mirko想这么干)重排（开着的猪圈中的）剩余的猪啦，啦，啦。。。。注意，猪圈的容量无穷大。请尽可能最大化他能卖出的猪的数量。
$\color{red} \text{注意:}$顾客来的顺序不可改变，顾客来后、调整完后猪圈门会关闭。
### 输入输出格式
第一行两个整数M、N($1\le M \le 1000,1\le N\le100$)，分别表示猪窝数与顾客数。
第二行有M个整数，表示每个猪圈的初始猪的数量(不小于0，不大于1000)。
接下来N行，第一个数A表示他有的钥匙数，接下来A个数表示有哪些猪圈的钥匙，最后一个数B表示他对猪的需求量。
输出只有一个数，表示最多能卖出的猪的数量。
### 样例输入输出
P.S.洛谷题面没给样例。。。到SPOJ上搬过来的。。。
**输入样例#1：**
```
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
```
**输出样例#1：**
```
7
```
**输入样例#2：**
```
6 6
6 3 2 0 1 3
2 1 2 0
1 3 3
1 1 1
2 2 3 8
2 4 5 2
2 4 6 6
```
**输出样例#2：**
```
15
```
**输入样例#3：**
```
11 5
1 2 2 1 0 2 4 1 1 1 2
5 1 2 3 4 5 3
4 1 2 6 7 5
2 3 8 1
3 3 6 11 5
3 8 9 10 3
```
**输出样例#3：**
```
17
```
题目描述
[English](/problems/MPIGS/en/) [Vietnamese](/problems/MPIGS/vn/) ```
Mirko works on a pig farm that consists of M locked pig-houses
and Mirko can't unlock any pig-house because he doesn't have the keys.
Customers come to the farm one after another. Each of them has keys
to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that
particular day are available to Mirko early in the morning so that
he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arives,
opens all pig-houses to which he has the key, Mirko sells a certain number
of pigs from all the unlocked pig-houses to him, and, if Mirko wants,
he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can
sell on that day
```
输入输出格式
输入格式
```
The first line of input file contains two integers M and N, 1 ≤ M ≤ 1000,
1 ≤ N ≤ 100, number of pig-houses and number of customers. Pig
houses are numbered from 1 to M and customers are numbered
from 1 to N.
The next line contains M integeres, for each pig-house initial number
of pigs. The number of pigs in each pig-house is greater or equal to
0 and less or equal to 1000.
The next N lines contains records about the customers in the following
form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B
It means that this customer has key to the pig-houses marked with
the numbers K1, K2, ..., KA
(sorted nondecreasingly ) and that he wants to buy B pigs. Numbers
A and B can be equal to 0.
```
输出格式
```
The first and only line of the output file should contain the number of
sold pigs.
```