영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 ≥ 1.
Then follow N lines, each containing first the number m_i ≥ 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 5000 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 100000 |
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.
예제
예제 1
3 2 5 15 2 10 20 1 60
260