Description

养猪场由$M$ 个上锁的猪舍组成，米尔科没有钥匙，所以不能打开任何猪舍。客户们纷纷来到农场。他们每个人都有一些猪舍的钥匙，想买一定数量的猪。米尔科一大早就得知当天参观农场的客户数量，他可以制定销售计划以最大限度地增加猪的销售数量。流程如下：

①客户到达，打开其有钥匙的所有猪舍；

②米尔科从所有已打开的猪舍向客户出售一定数量的猪，若米尔科愿意，则他可以在已打开的猪舍之间重新分配剩余的猪。每个猪舍都可以放无限头猪。

Format

Input

第$1$行包含两个整数$M$ 和$N （1≤M ≤1000，1≤N≤100）$，表示猪舍数量和客户数量。猪舍编号为$1～M$ ，客户编号为$1～N$。下一行包含$M$个整数，表示每个猪舍的初始猪数量。每个猪舍中猪的数量都大于或等于$0$，小于或等于$1000$。接下来的$N$ 行包含“$A , K_1 , K_2 , …, K_A , B$”形式的客户记录（第$i$个客户的记录在第$i +2$行中），表示这个客户有$K_1 , K_2 , …, K_A$ （非递减排序）的猪舍钥 匙，想买$B$ 头猪。数字$A$ 和$B$ 可以等于$0$。

Output

单行输出可以出售的猪的最大数量。

Samples

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

7

来源

POJ1149