← 返回题目列表

Codeforces · 1090/A

A. 公司合并

中文机器翻译题面 查看原题

企业集团由 $$$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$$$。