A. Company Merging

A conglomerate consists of nn companies. To make managing easier, their owners have decided to merge all companies into one. By law, it is only possible to merge two companies, so the owners plan to select two companies, merge them into one, and continue doing so until there is only one company left.

But anti-monopoly service forbids to merge companies if they suspect unfriendly absorption. The criterion they use is the difference in maximum salaries between two companies. Merging is allowed only if the maximum salaries are equal.

To fulfill the anti-monopoly requirements, the owners can change salaries in their companies before merging. But the labor union insists on two conditions: it is only allowed to increase salaries, moreover all the employees in one company must get the same increase.

Sure enough, the owners want to minimize the total increase of all salaries in all companies. Help them find the minimal possible increase that will allow them to merge companies into one.

Input

The first line contains a single integer nn — the number of companies in the conglomerate (1≤n≤2⋅1051≤n≤2⋅105). Each of the next nn lines describes a company.

A company description start with an integer mimi — the number of its employees (1≤mi≤2⋅1051≤mi≤2⋅105). Then mimi integers follow: the salaries of the employees. All salaries are positive and do not exceed 109109.

The total number of employees in all companies does not exceed 2⋅1052⋅105.

Output

Output a single integer — the minimal total increase of all employees that allows to merge all companies.

Example

input

3
2 4 3
2 2 1
3 1 1 1

output

13

题意：有n个公司，每个公司m个员工，这n个公司两两合并，只有当两个公司员工的最大工资相等时才能合并。员工的工资增长必须是全体一起增加相同的数额。求合并n个公司需要的最小增加工资值。

 

记录每个公司的员工数目和最大工资，按最大工资由大到小排序，依次合并相邻的两个公司，记录每个公司的人数*工资增长值即可。

数据范围在2*10^5 * 2*10^5，需要开long long

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
struct ac
{
	ll num,maxn;
}a[1000005];

bool cmp(ac x,ac y)
{
	return x.maxn>y.maxn;
}
 
int main()
{
	ll n,m,i,j,tmp,Max,sum=0;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>m;
		a[i].maxn=0;
		a[i].num=m;
		for(j=0;j<m;j++)
		{
			cin>>tmp;
			a[i].maxn=max(a[i].maxn,tmp);
		}
	}
	sort(a,a+n,cmp);
	for(i=0;i<n-1;i++)
	{
		sum+=(a[i].maxn-a[i+1].maxn)*a[i+1].num;
		a[i+1].maxn=a[i].maxn;
	}
	cout<<sum<<endl;
	return 0;
}