Оголошення про вакансії
Ваш університет має вакансії для студентів, і адміністрація потребує вашої допомоги у призначенні студентів на ці вакансії. Мета полягає в тому, щоб студенти обрали бажані позиції, а потім розподілити кожного студента на одну з позицій так, щоб досягти максимальної задоволеності.
Кожен студент обирає чотири позиції в порядку бажаності. Перша позиція є найбільш бажаною, наступна позиція є наступною за бажаністю, якщо перша позиція недоступна для цього студента, і так далі.
Студенти мають старшинство, засноване на їхньому році навчання. Вибори студентів третього курсу повинні мати більшу вагу, ніж вибори студентів першого курсу.
Адміністрація хоче, щоб ви використовували наступну матрицю задоволеності:
Ваше завдання полягає в тому, щоб призначити студентів на позиції таким чином, щоб максимізувати суму задоволеності всіх студентів відповідно до наведеної вище матриці. Кожен студент повинен отримати позицію, але не всі позиції можуть бути заповнені.
Вхідні дані
У вхідних даних буде декілька тестових випадків. Кожен тестовий випадок починається з двох цілих чисел, 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.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число, яке вказує на максимальну досяжну задоволеність. Не виводьте пробілів і не виводьте порожнього рядка між відповідями.