A. Объединение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Чтобы выполнить требование антимонопольной службы, владельцы могут перед объединением изменить зарплаты в одной из объединяемых компаний. Однако профсоюз настаивает на двух требованиях: разрешается только увеличивать зарплаты, кроме того, всем сотрудникам одной и той же компании необходимо увеличивать зарплату на одну и ту же величину.

Разумеется, руководство хочет минимизировать суммарное повышение всех зарплат. Помогите им выяснить, на какую минимальную суммарную величину придется повысить зарплаты сотрудников всех компаний в процессе объединения их в одну компанию.

Входные данные

В первой строке входных данных находится целое число $$$n$$$ — количество компаний в конгломерате ($$$1 \le n \le 2 \cdot 10^5$$$). В следующих $$$n$$$ строках описаны сами компании, каждая в своей строке.

Описание каждой компании начинается с целого числа $$$m_i$$$ — количества сотрудников в ней ($$$1 \le m_i \le 2 \cdot 10^5$$$). Далее идут $$$m_i$$$ целых чисел — зарплаты сотрудников. Все зарплаты положительны и не превосходят $$$10^9$$$. Гарантируется, что общее количество сотрудников во всех компаниях не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите единственное число — минимальную суммарную величину, на которую придется повысить зарплаты сотрудникам.

Пример
Входные данные
3
2 4 3
2 2 1
3 1 1 1
Выходные данные
13
Примечание

Один из оптимальных вариантов объединения компаний в примере следующий. Сначала объединим первую и вторую компании, перед этим повысив зарплаты во второй компании на $$$2$$$. Теперь в конгломерате две компании с зарплатами $$$[4, 3, 4, 3]$$$ и $$$[1, 1, 1]$$$. Чтобы их объединить, повысим зарплаты во второй из них на $$$3$$$. Итого суммарное увеличение составило $$$2 + 2 + 3 + 3 + 3 = 13$$$.