Проблемне завдання
У різних змаганнях з програмування потрібні різні типи задач. Наприклад, максимальний розмір масиву для задачі TopCoder становить лише 50, і ви точно не можете дати задачу на Суфіксне Дерево на IOI, оскільки учасники не матимуть шансу її розв'язати (за винятком деяких дуже досвідчених). Таким чином, не кожна задача підходить для кожного змагання.
Ви готуєте набори задач для N різних змагань. Ці змагання вимагають різну кількість задач, залежно від типу. Наприклад, набір задач у стилі ACM ICPC зазвичай має 10 задач, TopCoder SRM – 5 і так далі.
На щастя, ви вже підготували M різних задач. Для кожної задачі ви визначили набір змагань, до яких ви можете дати цю задачу. Також ви знаєте необхідну кількість задач для кожного змагання.
Визначте максимальну кількість різних змагань, для яких ви можете одночасно скласти повні набори задач з даного набору задач. Усі задачі в наборах задач повинні бути унікальними, тобто жодна задача не може бути використана двічі в різних наборах задач.
Вхідні дані
Вхідний файл містить декілька тестових випадків.
Перша строка кожного тестового випадку містить 2 цілі числа N та M (1 ≤ N ≤ 15, 0 ≤ M ≤ 50) – кількість різних змагань та кількість підготовлених задач. Кожен з наступних N рядків містить назву змагання, за якою слідує необхідна кількість задач для цього змагання. Назва змагання складається з малих та великих латинських літер та/або цифр, не є порожньою і не перевищує 100 символів. Назви змагань чутливі до регістру. Гарантується, що всі назви змагань будуть попарно різними. Необхідна кількість задач не перевищує 100.
Кожен з наступних M рядків містить (можливо порожній) список прийнятних назв змагань для кожної задачі, розділених одним пробілом. Гарантується, що всі назви змагань будуть правильними (тобто, зазначеними в попередньому розділі поточного тестового випадку) та унікальними.
Рядок, що містить два нулі, вказує на кінець вхідного файлу.
Вихідні дані
Для кожного тестового випадку виведіть відповідь для цього випадку на новому рядку, як показано в прикладі виходу.