Job Postings

Your university offers jobs for students, and the administration needs your help assigning students to jobs so that overall satisfaction is maximized. Students rank the positions they want, and each student is then allocated to one of those positions.

Each student selects four positions, in order of desirability: the first is the most wanted, the second is the next most wanted (used when the first is not available to that student), and so on.

Students have seniority based on their year of study. A third-year student's selection carries more weight than a first-year student's selection.

The administration wants you to use the following satisfaction matrix:

Assign students to positions so that the sum of every student's satisfaction is maximized. Each student must receive a position, but not every position needs to be filled.

The input contains several test cases.

Each test case begins with two integers $n$ ($4 \le n \le 140$) and $m$ ($1 \le m \le 70$), where $n$ is the number of job postings and $m$ is the number of students. Each of the next $n$ lines contains a single integer $p$ ($1 \le p \le 10$), the number of positions available for that job posting. The postings are listed in order, from job $0$ to job $n-1$.

The next $m$ lines describe the students. Each line contains five integers:

y c1 c2 c3 c4

Here $y$ ($y \in {1, 2, 3}$) is the student's year of study, and $c_1, c_2, c_3, c_4$ ($0 \le c_i < n$, all four distinct) are the student's chosen job postings in order of preference.

Every test case is guaranteed to admit an assignment in which every student receives one of the postings on their choice list.

The input ends with a line containing two zeros.

For each test case, output a single integer: the maximum achievable satisfaction. Do not print extra spaces, and do not print a blank line between answers.