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