구인 공고

당신의 대학에는 학생들이 지원할 수 있는 일자리가 있으며, 행정처는 전체 만족도가 최대가 되도록 학생을 일자리에 배정하는 일을 도와줄 사람이 필요합니다. 학생들은 원하는 자리를 선호 순서대로 고르고, 각 학생은 그중 하나의 자리에 배정됩니다.

각 학생은 선호하는 순서대로 네 개의 자리를 선택합니다. 첫 번째가 가장 원하는 자리이고, 두 번째는 그다음으로 원하는 자리이며(첫 번째 자리를 배정받지 못했을 때 사용), 이런 식으로 이어집니다.

학생에게는 학년에 따른 우선순위가 있습니다. 3학년 학생의 선택은 1학년 학생의 선택보다 더 큰 가중치를 가집니다.

행정처는 다음 만족도 표를 사용하기를 원합니다.

모든 학생의 만족도 합이 최대가 되도록 학생을 자리에 배정하세요. 각 학생은 반드시 하나의 자리를 배정받아야 하지만, 모든 자리가 채워질 필요는 없습니다.

입력에는 여러 개의 테스트 케이스가 있습니다.

각 테스트 케이스는 두 정수 $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 \in \{1, 2, 3\}$)는 학생의 학년이고, $c_1, c_2, c_3, c_4$ ($0 \le c_i < n$, 네 값 모두 서로 다름)는 학생이 선호 순서대로 고른 공고 번호입니다.

모든 테스트 케이스에서, 각 학생이 자신의 선택 목록에 있는 공고 중 하나를 배정받을 수 있는 배정이 반드시 존재함이 보장됩니다.

입력은 두 개의 0이 적힌 줄로 끝납니다.

각 테스트 케이스마다 달성 가능한 최대 만족도를 정수 하나로 출력하세요. 불필요한 공백을 출력하지 말고, 답 사이에 빈 줄을 출력하지 마세요.