Чарівні мішки#12975

Чарівні мішки

4 секунди
512 мегабайтів
Складна

У Далекому-Далекому королівстві, Шрек і його друзі натрапили на дивовижну головоломку, заховану глибоко в Зачарованому лісі. Осел, який завжди шукав нові пригоди, виявив містичних мішків, кожен з яких містить унікальну колекцію магічних предметів. Кожен предмет має певну магічну силу, представлену цілим числом.

Як завжди, Осел не зміг устояти і перетворив це на гру. «Гей, Шреку, я кидаю тобі виклик: зроби кожну пару мішків доброю, при цьому залишаючи мінімальну кількість магічних предметів загалом!» — вигукнув він. Шрек, трохи роздратований, але готовий до завдання, запитав: «Що ти маєш на увазі під доброю, Осле?»

«Пара мішків добра, якщо ти можеш вибрати один магічний предмет з одного мішка, що сильніший за один з іншого мішка, і ще один, що слабший. Так магія залишатиметься збалансованою!» — пояснив Осел з хитрою усмішкою.

Більш формально, пара мішків та є доброю якщо існують елементи a_1 \in A та b_1 \in B такі що a_1 < b_1 та існують елементи a_2 \in A та b_2 \in B такі що a_2 > b_2. It’s possible that a_1 = a_2 or b_1 = b_2.

Тепер завдання Шрека — з’ясувати: скільки мінімально магічних предметів повинно залишитись у всіх мішках, щоб кожна пара мішків залишалась доброю, якщо вона була доброю спочатку? Звісно, кожен мішок повинен містити хоча б один магічний предмет, щоб магія не зникла.

Вхідні дані

У першому рядку задано одне ціле число — кількість мішків.

Наступні рядків містять ціле часло k_i — розмір -того мішка. Після нього записано k_i цілих чисел a_{ij} — магічні сили предметів в -тому мішку.

2 \le n \le 2 \cdot 10^5,

1 \le k_i,

\sum k_i \le 5 \cdot 10^5,

1 \le a_{ij} \le 10^9,

всі a_{ij} є різними, навіть об’єкти в різних мішках не можуть мати однакову магічну силу.

Вихідні дані

Виведіть одне число — мінімальну загальну кількість магічних предметів, що залишаться у мішках.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі, кожна пара мішків є початково доброю. Один з можливих розв’язків:

  1. Об’єкт з силою 7.

  2. Об’єкти з силами 1 і 9.

  3. Об’єкти з силами 2 і 8.

  4. Об’єкти з силами 6 і 12.

У другому прикладі жодна пара мішків не є доброю, проте все ще в кожному мішку повинен залишитися хоча б один об’єкт.