실습 발표 계획

아, 대학교. 지식의 보루이자 교육의 메카이며 관료주의의 중심이다.

Wille와 Kaski는 현재 전산실에서 과목의 실습을 발표하기 위해 기다리고 있다. 실습 발표를 기다리는 그룹은 총 $N$개이다. 그룹 $i$은 서로 다른 실습 $m_i$개를 발표하며, 실습 $j$에는 $a_{i, j}$분이 걸린다.

공평하게도 모든 그룹은 발표하기 위해 정말 오랜 시간을 기다려야 한다. 발표를 받는 교사는 단 한 명뿐이며, 각 그룹이 자신의 모든 실습을 한 번에 발표하게 하면 다른 그룹 때문에 불필요하게 기다릴 필요가 없을 것이다! 따라서 교사는 겉보기에는 제멋대로인 순서로 발표를 받는다...

Kashi는 이제 참을 만큼 참았다. 집에 가서 Pokémon을 하고 싶은 그녀는 발표 방식의 비효율성에 불평하고 있다. 이 시스템이 얼마나 비효율적인지 보여 주기 위해, 그녀는 가능한 가장 긴 총 대기 시간을 계산하고 교사의 방식이 이 값에 얼마나 가까운지 보여 주려고 한다.

어떤 그룹이 시각 $a$에 첫 실습 발표를 시작하고 시각 $b$에 마지막 실습 발표를 마친다고 가정하자. 그러면 그 그룹의 대기 시간은 $b - a$이다. 총 대기 시간은 모든 그룹의 대기 시간의 합이다.

한 그룹이 실습을 발표해야 하는 순서는 입력으로 주어진 순서와 같아야 한다.

채점

제출한 풀이는 여러 그룹에 대해 채점된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

1번부터 4번까지의 그룹에서는 모든 $m_i$의 합이 최대 $5\,000$이다.

그룹  |  점수  |  제약 조건

1 | 30 | 모든 $m_i$의 합은 최대 10이다

2 | 17 | 모든 실습의 길이가 같다

3 | 13 | 모든 그룹이 발표할 실습을 정확히 2개씩 가진다

4 | 18 |

5 | 22 | 모든 $m_i$의 합은 최대 $100\,000$이다

첫 번째 줄에는 정수 $N \ge 1$ 하나가 주어진다.

이후 $N$개의 줄이 주어지며, 각 줄에는 먼저 수 $m_i \ge 1$이 주어지고, 이어서 1와 60 사이인 $m_i$개의 정수 $a_{i,j}$이 주어진다.

가능한 모든 발표 순서에 걸쳐 학생들의 가능한 가장 긴 총 대기 시간을 나타내는 수 하나를 출력한다.

주어진 예제에서는 세 그룹이 실습을 발표해야 한다. 첫 번째 그룹에는 각각 5분과 15분이 걸리는 실습이 있고, 두 번째 그룹의 실습에는 10분과 20분이 걸리며, 세 번째 그룹에는 한 시간 내내 걸리는 실습 하나가 있다.

순서 $5, 10, 60, 20, 15$을 선택하면 세 번째 그룹은 60분만 기다린다. 두 번째 그룹은 자신의 실습뿐만 아니라 세 번째 그룹의 실습도 기다려야 하므로 $10+60+20 = 90$분이 걸린다. 반면 첫 번째 그룹에는 $5 + 10 + 60 + 20 + 15 = 110$분이 걸린다.

이를 합하면 $60 + 90 + 110 = 260$분이다.

순서 10, 15, 60, 20, 5을 사용했다면 $265$이라는 더 나쁜 시간이 나왔겠지만, 이는 허용되지 않는다. 그룹 1은 첫 번째 실습보다 두 번째 실습을 먼저 발표할 수 없다.