Объединение

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

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

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

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

Входные данные
В первой строке входных данных находится целое число n — количество компаний в конгломерате (1≤n≤2⋅105). В следующих n строках описаны сами компании, каждая в своей строке.

Описание каждой компании начинается с целого числа mi — количества сотрудников в ней (1≤mi≤2⋅105). Далее идут mi целых чисел — зарплаты сотрудников. Все зарплаты положительны и не превосходят 109. Гарантируется, что общее количество сотрудников во всех компаниях не превосходит 2⋅105.

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

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

0