1. 超市

1. 超市

【题目描述】
超市正在举行一个活动,该活动的规则如下:
想要参与的顾客会将他购物的账单放入纸箱中,账单上写有顾客的联系方式和购物的金额。每天超市关门前纸箱中金额最大、最小的两张帐单被取出,付款金额最大的顾客将获得一笔奖金,价值为取出的两张帐单的金额之差;为了不重复计算,取出的两张帐单不再放回箱子,而剩下的帐单仍保留在箱中,进行第二天的活动。
顾客很多,因此可假定:每天活动结束时,箱中至少有两张帐单以供取出。
小h也参加了这次活动,他想知道整个活动期间超市付出的奖金总额是多少?

【输入数据】
第一行是一个整数n,表示活动历时的天数。
以下的n行,每行包含若干由空格分隔的非负整数。第i+1行的数表示在第i天投入箱子的账单金额。每行的第一个数是一个整数k,表示当日账单的数目。后面的k个正整数代表这k笔账单的金额。

【输出数据】
输出一个数,表示活动期间超市付出的奖金总额。

Sample 1

Input

5 
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2

Output

19

Limitation

1s, 128MiB for each test case.
【数据范围】
设s为整个活动中涉及到的账单笔数。
30%的数据满足n≤100,s≤10000。
70%的数据满足s≤10^5。
100%的数据满足1≤n≤5000,0≤k≤10^5,s≤10^6,每笔账单的金额不超过10^6。

信息

难度
7
分类
(无)
标签
递交数
26
已通过
6
通过率
23%
上传者

相关

在下列训练计划中:

哈希表及set容器的应用