# 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.