Problem : 74 - 特價

Problem Statistics

Solved Member: 41　　Submission: 218　　User Tried: 43

Statement:

有家超市正在辦促銷活動，活動總共進行n天。

這個活動的規則如下：

1.客人買完東西之後，依照他所購買的金額，投到抽獎箱裡面。
2.每一天營業結束之後，會從抽獎箱裡面拿出金額最大與最小的任意2張抽獎卷。這2筆金額的差額就是今天的獎金。
3.為了避免重複中獎，上面抽到的兩張抽獎卷就會拿出抽獎箱。其他的抽獎卷可以隔天繼續抽獎。
4.上面被抽到的2人，平分這筆獎金。

每天都有若干個客人來消費，由於這家超市非常的大，你可以假設每天拿完2張之後隔天至少還有2張可以抽。
你的任務就是要計算這家超市總共要付多少獎金。

Input:Output:

第1行有1個整數n，代表活動進行了n(1 <= n <= 5000)天。
接下來n行每一行最剛開始有1個數字k(0 <= k <= 100000)，代表這一天有k個人消費，後面接著k個數字代表每個人的消費金額。
你可以假設所有人的消費金額皆在1000000以下，並且，這n天的總人數<=1000000。

輸出1個整數，代表超市舉辦這個活動需要花費多少錢的獎金。

Sample Input:Sample Output:

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

Source:

POI 7 Stage 3

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	300ms	32768kb
1	300ms	32768kb	10
2	300ms	32768kb	10
3	300ms	32768kb	10
4	300ms	32768kb	10
5	300ms	32768kb	10
6	300ms	32768kb	10
7	1500ms	32768kb	10
8	1500ms	32768kb	10
9	4000ms	32768kb	10
10	4000ms	32768kb	10