Задача №114477. Объединение
В конгломерат входит \(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\).
Выведите единственное число — минимальную суммарную величину, на которую придется повысить зарплаты сотрудникам.
Один из оптимальных вариантов объединения компаний в примере следующий. Сначала объединим первую и вторую компании, перед этим повысив зарплаты во второй компании на \(2\). Теперь в конгломерате две компании с зарплатами \([4, 3, 4, 3]\) и \([1, 1, 1]\). Чтобы их объединить, повысим зарплаты во второй из них на \(3\). Итого суммарное увеличение составило \(2 + 2 + 3 + 3 + 3 = 13\).
3 2 4 3 2 2 1 3 1 1 1
13