Description

S市有个地下商人团体，为顾客提供一种来路很窄的宝石，为了避免被条子一窝端，他们将宝石藏在m个不同的地方，每个地方都需要密码才能进入。
组织内部经过长期的勾心斗角最终确定了交易规则：藏宝石的人知道密码（当然也知道地点），但不能与顾客、接待人联系，接待人知道地点、地点藏匿的宝石数量，但不知道密码。一轮交易开始，接待人在接头地点待机，在规定时间之前不得移动；藏宝人前往城市各处，以暗号的形式写下接头地点、接头时限，并附上一批密码及对应地点的编号。有心人如果能识别这一系列暗号，就会在时限前赶往接头地点，报上自己知道密码的地点编号和期望购买的宝石数量。接头时限过后，接待人会根据这些信息安排顾客的顺序，依次带他们前往藏宝地点，向他们出售一定数量的宝石。出于利益最大化考虑，上头特别允许：接待人可以重新分配当前接待的顾客知道密码的所有地点藏匿的宝石，但如果没能使利益最大化，就要处分接待人（上头数学很好）。
但新来的接待人V数学不是很好，想请你帮忙安排一下接待计划，并向你承诺了高到诡异的报酬，不知你愿不愿意呢？

Format

Input

第一行两个整数m, n. 1 <= m <= 1000, 1 <= n <= 100, 分别表示藏宝地点数和顾客数。
第二行包含m个整数，表示各个地点藏匿的宝石数量。（不小于0，不大于1000）
接下来n行的格式为：N, a1, a2,..., aN, b.
其中N为顾客知道的藏宝地点数，ai为地点对应的编号 (1 <= ai <= m), b为期望购买数。(N和b可以等于0)

Output

一个整数，表示最多能卖出多少宝石。

Sample 1

Input

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

Output

7

Limitation

1s, 10000KiB for each test case.