루미 알고리즘

#1386플래티넘Lab planning

PO 2016 결선코딩출제 Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupScoreConstraings
130the sum of all m_i is at most 10
217all labs have the same length
313all groups have exactly 2 labs to present
418
522the 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

출처 표기

출처: Programmeringsolympiaden 2016년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.