1592. 公司合并
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 一个大型企业集团由 $n$ 家公司组成。为了简化管理，其所有者决定将所有公司合并为一个公司。根据法律，只能合并两个公司，因此所有者计划选择两个公司，将它们合并为一个公司，并继续这样做，直到只剩下一个公司。 但是，反垄断机构如果怀疑公司受到不善意的合并，则禁止合并公司。他们判断的标准是两家公司之间的最高工资之差，仅当最高工资金相等时才允许合并。 为了满足反垄断的要求，公司的拥有者可以在合并之前更改其公司的薪水。但是职工联合会坚持两个条件：只允许加薪，而且一家公司的所有雇员必须获得相同的加薪。 当然，拥有者希望将所有公司中所有工资的加薪总和减到最小。 帮助他们找到可能的最小的和，使他们能够将公司合并为一个公司。 ## 输入格式 第一行包含一个整数 $n$，表示集团中公司的数量。 接下来的 $n$ 行分别描述了一家公司。 公司描述先给出一个整数 $m_i$ 表示该公司员工人数。然后是 $m_i$个整数表示员工的薪水。 所有薪水均为正数，且不超过$10^9$。 所有公司员工数量总和不超过 $2 \cdot 10^5$ - $1 \le n \le 2 \cdot 10 ^ 5$ - $1 \le m_i \le 2 \cdot 10 ^ 5$ ## 输出格式 在一行中输出一个整数表示最小总加薪 ## 数据范围 ... ## 输入 ```in1 3 2 4 3 2 2 1 3 1 1 1 ``` ## 输出 ```out1 13 ``` ## 提示