Підтримую всіх#11746

Підтримую всіх

1 секунда

128 мегабайтів

Середня

Аліса відвідує спортивну подію за участю багатьох національних команд, і для неї важливо одне: підтримати кожну країну.

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

Кожен олівець і кожен значок коштують $1$ , але її бюджет обмежений... Чи зможете Ви допомогти їй знайти мінімальну суму, яку вона має витратити, щоби підтримати всі країни?

Вхідні дані

Перший рядок містить два цілих числа $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} попарно різні.

Вихідні дані

Виведіть одне число: мінімальну суму, яку Аліса може витратити на олівці та значки, щоби презентувати кожну країну.

Приклади

Приклад 1. Перші три країни можуть бути Францією, Нідерландами та Чеською Республікою, всі вони представлені синім $(1)$ , білим $(4)$ і червоним $(5)$ . Наступні три країни можуть бути Італією, Угорщиною та Болгарією із зеленим $(3)$ , білим $(4)$ та червоним $(5)$ . Остання країна може бути Німеччиною, з чорним $(2)$ , червоним $(5)$ і жовтим $(6)$ . Мінімальна вартість — $5$ : ми купуємо чотири олівці (синій, зелений, білий та червоний) та один значок (для Німеччини).

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

Приклад 1

Приклад 2