PRO  Promotion
A large Bytelandian supermarket chain has asked you to write a program for the simulating costs of a promotion being prepared.
The promotion has to follow the following rules:
 A customer who wants to participate in the promotion, writes on the receipt, paid by himself, his personal details and throws it into a special ballot box.
 At the end of every day of the promotion, two bills are taken out from the ballot box:
 first, the receipt amounting to the largest sum is chosen,
 then the receipt amounting to the smallest sum is chosen;
 To avoid multiple prizes for one purchase, both bills selected according to the above rules are not returned to the ballot box, but all remaining bills still participate in the promotion.
The turnover of the supermarket is very big, thus an assumption can be made, that at the end of every day, before taking out receipts amounting to the largest and the smallest sum, there are at least 2 receipts in the ballot box.
Your task is to compute (on the basis of information about prices on receipts thrown into the ballot box on each day of promotion) what the total cost of prizes during the whole promotion will be.
Write a program, which: reads from the standard input a list of prices on receipts thrown into the ballot box on each day of the promotion, computes the total cost of prizes paid in consecutive days of promotion, then writes the result to the standard output.
Input
The first line of the input contains one positive integer n (1 <= n <= 5000), which is the duration of promotion in days. Each of the next n lines consists of a sequence of nonnegative integers separated by single spaces. Numbers in the (i+1)th line of the file represent prices on receipts thrown into the ballot box on the ith day of promotion. The first integer in the line is k, 0 <= k <= 10^5, the number of receipts on the day, and the next k numbers are positive integers standing for the sums on receipts; none of these numbers is larger than 10^6.
The total number of bills thrown into the ballot box during the whole promotion does not exceed 10^6.
Output
The output should contain exactly one integer, equal to the total cost of prizes paid during the whole promotion.
Example
Input: 5 3 1 2 3 2 1 1 4 10 5 5 1 0 1 2 Output: 19
hide comments
code0monkey1:
20171103 15:01:40
Logically 2 priority ques ( one max , one min ) should work.. but for some odd reason TLE on test case 7 ! 

heisenberg0820:
20170614 10:13:27
Multiset :) 

siddharth_0196:
20170324 16:24:23
No DSU! Implementation of Priority_queue! :) 

neeraj745:
20170314 00:12:30
@ ARBY thanks for mentioning that we have to store sum in long long int, it also costed me wrong answer without using that. 

Madhukar Reddy:
20160904 11:29:16
Please increase the time limit, it is impossible for solutions in slower languages like python to be accepted with current time limit.


entcat:
20160901 23:08:44
multisets FTW!!


karan_batra:
20160819 13:16:01
STL YEAHHH :) 

thelazycoder:
20160130 00:00:46
Weak test cases ! 

SangKuan:
20150817 07:53:22
stl and long long int 

ARBY:
20150816 12:10:45
Don't forget to use long long for storing the sum. Cost me 1 WA. Last edit: 20150816 12:16:43 
Added by:  Duc 
Date:  20060124 
Time limit:  0.147s0.672s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  VII Polish Olympiad In Informatics 2000, stage III 