eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Стоимость прогулки

Стоимость прогулки

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Есть несколько катеров и большая группа людей. Для каждого катера известна его вместимость. Для каждого человека известно, на каких катерах он предпочел бы прокатиться. После опыта предыдущей задачи владельцы катеров выяснили, что подобный способ оплаты может быть весьма невыгоден. Поэтому было решено брать одинаковую плату за каждый используемый катер, независимо от количества людей на нем. Требуется распределить людей по катерам на одну морскую прогулку так, чтобы минимизировать количество используемых катеров.

Вхідні дані

Два числа N и K (1N16, 1K100) - количество катеров и людей. N строк по одному числу в каждой - s (0 s100) - количество мест в катере. Далее K строк, в каждой из которых дано число t - количество катеров, которые подходят текущему человеку, после чего следует список номеров этих катеров. Все номера в пределах от 1 до N, каждый номер встречается не более одного раза.

Вихідні дані

Одно число - минимальное количество катеров, либо -1, если всех людей рассадить по катерам не получится.

Приклад

Вхідні дані #1
3 5
1
2
3
3 1 2 3
2 1 2
1 1
2 1 2
3 1 2 3
Вихідні дані #1
3
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь