TopCoder

Thumb 20121228010347445
小翔
嘿嘿嘿~~~~

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

32.7% (16/49)

Description

TIOJ賣場為了應付低迷的買氣而舉辦了促銷活動。

參加這活動的消費者在自己的發票後面寫上自己的資料投入指定的箱子,在每次的銷售活動結束後,箱子中最高以及最低消費的發票將會被選出,而消費最多的顧客將可以得到一筆獎金,獎金的數目等於兩張發票金額的差。

為了避免一次消費得到很多次獎金(這樣只要一次買很多就可以賺到翻過來又翻過去了),選出的那兩張發票將不會放回箱子裡,但剩下的發票則可以繼續參加隔天的活動。

你是TIOJ賣場的小員工,你知道每天投入的所有的帳單數量與金額,你的任務就是要計算出賣場總共要發出多少獎金。

Input Format

本題有多筆測試資料,請以EOF作為結束

每筆資料的:

第一行有一個數字n,代表活動持續了n天 (n<=5000)

接下來有n行,代表每一天的發票數量以及金額

每一行的第一個數字k代表該天有多少張發票,之後跟著k個數字mi分別代表發票的金額 (mi<=106)

(我們保證發票的數量少於106張)

Output Format

對於每筆資料輸出一個數字p,代表TIOJ賣場總共要送出p元的獎金

Sample Input

2
3 10 100 20
2 1000 20

Sample Output

1070

Hints

Problem Source

原TIOJ1415 / 快樂暑假營複習賽。Problem Setter:hallogameboy

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2500 65536 65536