大学有提供给学生的职位，管理部门需要你帮助他们将学生分配到这些职位上。目标是让学生选择他们期望的职位，然后将每位学生分配到一个职位，以实现最大化的满意度。

每位学生按期望程度从高到低选择四个职位。第一个职位是最想去的，下一个职位是次想去的，以此类推，如果第一个职位对该学生不可用，则考虑下一个。

学生拥有基于其学习年限的资历。三年级学生的志愿权重应高于一年级学生。

管理部门要求你使用以下满意度矩阵：

你的任务是以最大化所有学生满意度总和的方式将学生分配到职位。每位学生必须获得一个职位，但并非所有职位都必须被填满。

输入格式

输入包含多个测试用例。每个测试用例以两个整数 $n$ ($4 \le n \le 140$) 和 $m$ ($1 \le m \le 70$) 开头，其中 $n$ 是职位数量，$m$ 是学生数量。接下来的 $n$ 行，每行包含一个整数 $p$ ($1 \le p \le 10$)，表示该职位可提供的名额数量。职位按顺序从职位 $0$ 到职位 $n-1$ 列出。

职位信息之后是 $m$ 行描述学生的信息。每行包含五个整数： $y \ c1 \ c2 \ c3 \ c4$

其中 $y$ ($y=1, 2$ 或 $3$) 是学生的年限，$c1, c2, c3$ 和 $c4$ ($0 \le c1, c2, c3, c4 < n$，且四个值互不相同) 表示学生按偏好顺序选择的职位。

保证每个测试用例都存在一种方案，使得每位学生都能获得其选择列表中的一个职位。

输入以一行两个 $0$ 结束。

输出格式

对于每个测试用例，输出一个整数，表示可达到的最大满意度。输出不要包含空格，且答案之间不要输出空行。

样例

输入 1

4 4
1
1
1
1
1 0 1 2 3
2 0 1 2 3
3 0 1 2 3
3 0 1 2 3
4 4
4
4
4
4
1 0 1 2 3
2 0 1 2 3
3 0 1 2 3
3 0 1 2 3
0 0

输出 1

30
36