Вакансии

Ваш университет предлагает студентам работу, и администрация нуждается в вашей помощи для распределения студентов по вакансиям. Цель состоит в том, чтобы студенты выбрали желаемые должности, а затем распределить каждого студента на одну из должностей так, чтобы было достигнуто максимальное удовлетворение.

Каждый студент выбирает четыре должности в порядке предпочтения. Первая должность — самая желанная, следующая должность — следующая по желанию, если первая недоступна, и так далее.

Студенты имеют старшинство, основанное на их курсе обучения. Выборы студентов третьего курса должны иметь больший вес, чем выборы студентов первого курса.

Администрация хочет, чтобы вы использовали следующую матрицу удовлетворенности:

Ваша задача — распределить студентов по должностям так, чтобы максимизировать сумму удовлетворенности всех студентов в соответствии с вышеуказанной матрицей. Каждый студент должен получить должность, но не все должности могут быть заполнены.

Входные данные

Входные данные содержат несколько тестов. Каждый тест начинается с двух целых чисел, n (4 ≤ n ≤ 140) и m (1 ≤ m ≤ 70), где n — количество вакансий, а m — количество студентов. Каждая из следующих n строк содержит одно целое число p (1 ≤ p ≤ 10), указывающее количество позиций, доступных для этой вакансии. Вакансии перечислены по порядку, от работы 0 до работы n-1.

После списка вакансий следуют m строк, описывающих студентов. Каждая строка студента содержит пять целых чисел:

y c_1 c_2 c_3 c_4

Где y (y=1, 2 или 3) — курс студента, а c_1, c_2, c_3 и c_4 (0 ≤ c_1, c_2, c_3, c_4 < n, все четыре уникальны) указывают выбор студента по вакансиям в порядке предпочтения.

Гарантируется, что для каждого теста существует решение, при котором каждый студент может получить одну из позиций из своего списка предпочтений.

Ввод заканчивается строкой с двумя 0.

Выходные данные

Для каждого теста выведите одно целое число, которое указывает максимальное достижимое удовлетворение. Не выводите пробелы и не оставляйте пустую строку между ответами.