СЪЕЛ ОУЖАС.
Рабочее название задачи
Вирус Хексадесимал очень любит играть с числовыми множествами — пересекать их, объединять. В один прекрасный день она с удивлением обнаружила, что Сказзи, ее ручной сферический кот, объединил все множества в одно и съел результат! Надо было срочно что-то делать, и Хексадесимал полетела на рынок.
На рынке продается n числовых множеств. Вирус хочет купить такой набор множеств, что количество множеств в нем будет равно количеству чисел в его объединении. Из всех подходящих наборов множеств она готова выбрать только самый дешевый.
Но не все так просто! Поскольку в Мэйнфрейме царит рынок совершенной конкуренции, то известно, что объединение любых k множеств содержит не менее k различных чисел (для любого целого положительного k).
Помогите вирусу выбрать подходящий набор множеств. Этот набор может быть пустым.
Выходные данные
Выведите одно число — минимальную стоимость покупки такого набора из k множеств, что объединение множеств этого набора содержит ровно k чисел (
).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
2 2 3
1 3
10 20 -3
|
-3
|
|
2
|
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1
|
0
|
|
3
|
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1
|
-1
|