Lab planning
Ah, university. A bastion of knowledge, the Mecca of education, and the core of bureaucracy.
Wille and Kaski are currently waiting in a computer lab to present a lab in a course. In total, there are $N$ groups waiting to present their lab. Group $i$ is going to present $m_ i$ different labs, where lab $j$ takes $a_{i, j}$ minutes.
To be fair, all groups need to wait a really long time to present. There is only a single teacher taking presentations, and letting each group present all their labs in a single go would mean that they don’t have to wait unnecessarily for other groups! Therefore, the teacher takes presentations in a seemingly arbitrary order...
Kashi has had enough. She wants to go home and play Pokémon, and is complaining about the inefficiencies in the presentation scheme. To demonstrate how inefficient the system is, she’ll compute the longest possible total waiting time, and show just how close the teacher’s system is to this value.
Assume that a group starts presenting their first lab at time $a$, and completes their final lab at time $b$. Then its waiting time is $b - a$. The total waiting time is the sum of the waiting time over all groups.
The order in which a group must present its labs must be the same as the order they are given in the input.
Input
The first line contains a single integer $N \ge 1$.
Then follow $N$ lines, each containing first the number $m_ i \ge 1$, and then $m_ i$ integers $a_{i,j}$, all between 1 och 60.
Output
You should output a single number: the longest possible total waiting time for the students over all possible presentation orders.
Grading
Your solution will be tested on a number of groups. To get the points for a group, you must pass all test cases in the group.
The sum of all the $m_ i$ will be at most $5\, 000$ in the groups 1 through 4.
|
Group |
Score |
Constraings |
|
1 |
30 |
the sum of all $m_ i$ is at most 10 |
|
2 |
17 |
all labs have the same length |
|
3 |
13 |
all groups have exactly 2 labs to present |
|
4 |
18 |
|
|
5 |
22 |
the sum of all the $m_ i$ is at most $100\, 000$ |
Explanation
In the given sample, three groups need to present their labs: the first group has labs taking 5 and 15 minutes, the second group takes 10 and 20 minutes, and the third group has a single lab taking an entire hour.
If we choose the order $5, 10, 60, 20, 15$, the third group will wait only for 60 minutes. The second group will, besides their own labs, have to wait for the lab of the third group, and therefore take $10+60+20 = 90$ minutes. The first group will instead take $5 + 10 + 60 + 20 + 15 = 110$ minutes.
The sum of this is $60 + 90 + 110 = 260$ minutes.
Note that the order 10, 15, 60, 20, 5 would have resulted in a worse time of $265$, but this is not allowed: group 1 may not present their second lab before their first.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 5 15 2 10 20 1 60 |
260 |
