记录编号	8838	评测结果	AAAAAAA
题目名称	[POI 2000] 促销活动	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2008-12-22 20:43:11	内存使用	0.26 MiB

/* 
 * Problem: POI2000 pro
 * Author: Guo Jiabao
 * Time: 2008.12.22 20:35
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

class tTreap
{
	private:
		class tNode
		{
			public:
				tNode *left,*right;
				int v,fix;
				tNode(int tv): v(tv),left(0),right(0)
				{
					fix=rand();
				}
		};
		tNode *root;
		int R;
		void rot_r(tNode *&P)
		{
			tNode *Q=P->left;
			P->left=Q->right;
			Q->right=P;
			P=Q;
		}
		void rot_l(tNode *&P)
		{
			tNode *Q=P->right;
			P->right=Q->left;
			Q->left=P;
			P=Q;
		}
		void _ins(tNode *&P,int v)
		{
			if (!P)
				P=new tNode(v);
			else if (v<P->v)
			{
				_ins(P->left,v);
				if (P->left->fix < P->fix)
					rot_r(P);
			}
			else
			{
				_ins(P->right,v);
				if (P->right->fix < P->fix)
					rot_l(P);
			}
		}
		void _delete_max(tNode *&P)
		{
			if (P->right)
				_delete_max(P->right);
			else
			{
				R=P->v;
				tNode *T=P;
				P=P->left;
				delete T;
			}
		}
		void _delete_min(tNode *&P)
		{
			if (P->left)
				_delete_min(P->left);
			else
			{
				R=P->v;
				tNode *T=P;
				P=P->right;
				delete T;
			}
		}
	public:
		tTreap():root(0){}
		void ins(int v){_ins(root,v);}
		int delete_max() {_delete_max(root);return R;}
		int delete_min() {_delete_min(root);return R;}
};

int N,Ans;
tTreap Treap;

void init()
{
	freopen("prom.in","r",stdin);
	freopen("prom.out","w",stdout);
}

void solve()
{
	int M,v,A,B;
	scanf("%d",&N);
	for (int i=1;i<=N;i++)
	{
		scanf("%d",&M);
		for (int j=1;j<=M;j++)
		{
			scanf("%d",&v);
			Treap.ins(v);
		}
		A=Treap.delete_max();
		B=Treap.delete_min();
		Ans+=A-B;
	}
}

int main()
{
	init();
	solve();
	printf("%d",Ans);
	return 0;
}