Поддерживаю всех#11746

Поддерживаю всех

1 saniyə

128 meqabayt

Orta

Алиса посещает спортивное событие с участием множества национальных команд, и для неё важно одно: поддержать каждую страну.

Всего представлено $n$ стран, и Алиса может поддержать каждую страну одним из двух способов: либо нарисовать на себе её флаг, либо иметь значок с названием страны. У Алисы есть список, в котором для каждой страны указаны цвета, необходимые для создания её флага. Всего имеются $m$ цветов, которые могут встречаться в разных флагах, и в списке Алисы каждый цвет представлен целым числом от $1$ до $m$ .

Каждый карандаш и каждый значок стоят $1$ , но её бюджет ограничен... Сможете ли Вы помочь ей найти минимальную сумму, которую она может потратить, чтобы поддержать все страны?

Giriş

Первая строка содержит два целых числа $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000) и $m (1 \leq m \leq 100)$ m~(1 \le m \le 100). Затем следуют $2 n$ строк, сгруппированных по парам; $(2 i - 1)$ (2i - 1)-я и $2 i$ -я строки представляют $i$ -ю страну. Более конкретно, $(2 i - 1)$ (2i - 1)-я строка содержит одно целое число $k_{i} (1 \leq k_{i} \leq m, i \leq n)$ k_i~(1 \le k_i \le m, i \le n): количество цветов в флаге $i$ -й страны. Затем $2 i$ -я строка содержит $k_{i}$ k_i чисел $c_{i, 1}, c_{i, 2}, ..., c_{i, k_{i}} (1 \leq c_{i, j} \leq m, i \leq n, j \leq k_{i})$ c_{i,1}, c_{i,2}, ..., c_{i,k_i}~(1 \le c_{i,j} \le m, i \le n, j \le k_i), которые представляют цвета флага $i$ -й страны. Для всех $i \leq n$ i \le n, $k_{i}$ k_i цветов $c_{i, j}$ c_{i,j} попарно различны.

Çıxış

Выведите одно число: минимальную сумму, которую Алиса может потратить на карандаши и значки, чтобы представить каждую страну.

Nümunələr

Пример 1. Первые три страны могут быть Францией, Нидерландами и Чешской Республикой, все они представлены синим $(1)$ , белым $(4)$ и красным $(5)$ . Следующие три страны могут быть Италией, Венгрией и Болгарией с зелёным $(3)$ , белым $(4)$ и красным $(5)$ . Последняя страна может быть Германией, с чёрным $(2)$ , красным $(5)$ и жёлтым $(6)$ . Минимальная стоимость — $5$ : мы покупаем четыре карандаша (синий, зелёный, белый и красный) и один значок (для Германии).

Пример 2. Мы можем купить два карандаша для цветов $7$ и $11$ и приобрести два значка, потратив всего $4$ . Все шесть стран с цветами флага $7$ (красный) и $11$ (белый) могут быть Канадой, Индонезией, Японией, Мальтой, Монако и Польшей. Флаг Белиза содержит $12$ цветов, включая красный и белый, а пятой страной может быть Ботсвана.

Nümunə 1

Nümunə 2