题目描述

你在银行工作，需要协助$n$个客户按顺序取走他们存放在保险箱里的金币。银行有$m$个保险箱，客户按顺序到访，每个客户会打开自己拥有钥匙的所有保险箱，并试图取走$c_i$枚金币。若金币不足，客户会取走尽可能多的金币并投诉。

你可以在客户取金币时，调整其打开的保险箱内的金币数量（如转移金币），以最大化所有客户取走的金币总数。请计算这个最大值。

输入格式

第一行有两个正整数$m$和$n$，分别表示保险箱数量和客户数量。
第二行有$m$个非负整数，依次表示$1$号到$m$号保险箱初始的金币数量。
接下来$n$行，按客户到访顺序描述每个客户：

• 每行开头是一个非负整数$k$，接着有$k$个整数$a₁, a₂, ..., aₖ$（1~m）$，表示客户拥有钥匙的保险箱编号。
• 最后是一个非负整数$cᵢ$，表示客户需要的金币数量。

输入保证所有整数不超过$20000$，答案不超过$100000$。

输出格式

输出一个整数，表示所有客户能取走的金币总数的最大值。

样例

样例1
输入：

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

输出：

7  

样例2
输入：

2 3  
2 3  
2 1 2 1  
1 2 2  
1 2 2  

输出：

5  

样例3
输入：

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  

输出：

15  

数据范围与提示