Promotion

A large supermarket chain has asked you to write a program that simulates the cost of a promotion it is planning.

The promotion follows these rules:

• A customer who wants to take part writes their personal details on a receipt they have paid for and drops it into a special ballot box.
• At the end of each day of the promotion, two receipts are drawn from the box:
  • first, the receipt with the largest amount is chosen,
  • then the receipt with the smallest amount is chosen.
• The customer who paid the largest receipt receives a cash prize equal to the difference between the largest amount and the smallest amount.
• To stop a single purchase from winning several times, the two receipts drawn this way are not returned to the box; every remaining receipt stays in the promotion.

Business is brisk, so you may assume that at the end of every day, just before the largest and smallest receipts are drawn, the box always holds at least two receipts.

Given the receipt amounts dropped into the box on each day of the promotion, compute the total cost of all prizes paid over the whole promotion.

Your program should:

• read the list of receipt amounts dropped into the box on each day,
• compute the total cost of the prizes paid across the successive days,
• write the result to standard output.

The first line contains one positive integer $n$ ($1 \le n \le 5000$): the length of the promotion in days.

Each of the next $n$ lines describes one day. The $(i+1)$-th line lists the receipt amounts dropped into the box on day $i$. It begins with an integer $k$ ($0 \le k \le 10^5$), the number of receipts that day, followed by $k$ positive integers giving those receipt amounts; none of these amounts exceeds $10^6$.

The total number of receipts dropped into the box over the whole promotion does not exceed $10^6$.

Print exactly one integer: the total cost of the prizes paid during the whole promotion.