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