Призи Фастфуду#6396
Під час регіонального конкурсу канадська філія популярного ресторану швидкого харчування зазвичай організовує гру для просування свого бізнесу. Деякі страви супроводжуються наклейками, і певні колекції різних наклейок можна обміняти на грошові призи. Якщо для отримання призу потрібні наклейки типів T_1, T_2, ..., T_k, ви можете отримати цей приз, якщо маєте по наклейці кожного з типів T_1, T_2, ..., T_k. Кожна наклейка може бути використана лише для одного призу. Проте, ви можете отримати один і той самий приз кілька разів, якщо у вас є достатня кількість наклейок кожного типу. Жодні два призи не вимагають однакових наборів типів наклейок. Деякі наклейки можуть не підходити для отримання грошового призу (наприклад, наклейка на безкоштовний молочний коктейль).
Під час вашої подорожі на регіональний конкурс ваш тренер змусив вас їсти в цьому ресторані та зібрав усі наклейки разом. Скільки грошей може отримати ваш тренер?
Вхід складається з кількох тестових випадків. Перша строка вхідних даних містить одне ціле число, не більше , яке вказує кількість тестових випадків, що слідують. Кожен випадок починається з рядка, що містить два цілі числа (1 \leq n \leq 10) та (1 \leq m \leq 30), де — це кількість різних типів призів, а — це кількість різних типів наклейок (типи позначені , , ..., ). Наступні рядків описують призи. Кожен з цих рядків починається з цілого числа (1 \leq k \leq m), що вказує кількість типів наклейок, необхідних для отримання призу. Далі йдуть цілих чисел, що вказують типи наклейок, які потрібні. Останнє ціле число в кожному рядку — це (позитивна) грошова вартість призу (не більше ). Останній рядок кожного випадку містить невід'ємних цілих чисел, де -те число вказує кількість наклейок типу , які зібрав ваш тренер. Немає більше ніж наклейок кожного типу.
Для кожного випадку виведіть в одному рядку загальну вартість грошових призів, які можна отримати.
Приклад 1