Problem C
Labbplanering

Ah, universitetet. En kunskapens högborg, utbildningens Mecka, och byråkratins kärna.

Wille och Kashi sitter just nu och ska redovisa en datorlaboration i en kurs. Totalt är det $N$ grupper som sitter i datasalen och väntar på att få redovisa. Grupp $i$ ska redovisa totalt $m_ i$ olika moment, där moment $j$ tar $a_{i, j}$ minuter.

För att det ska vara rättvist måste alla grupper vänta jättelänge på sina redovisningar. Det finns nämligen bara en lärare som tar redovisningar, och att låta varje grupp redovisa samtliga av sina moment i ett enda svep skulle ju innebära att en grupp aldrig måste stanna kvar längre än nödvändigt! Därför tar läraren emot redovisning av ett moment i taget i en ganska godtycklig ordning...

Kashi har fått nog. Hon vill hem och spela Pokémon, och klagar på den ganska ineffektiva redovisningsordningen högljutt. För att demonstrera just hur ineffektivt detta system är tänker hon titta på vad den längsta möjliga totala väntetiden är, och visa hur nära lärarens system är till detta.

Antag att en grupp börjar redovisa sitt första moment vid tid $a$, och blir färdig med redovisningen av sitt sista moment vid tid $b$. Då är väntetiden för denna grupp $b - a$. Den totala väntetiden är väntetiden summerad över alla grupper som redovisar.

Ordningen i vilken en grupps moment ska redovisas måste vara som i indata.

Input

Den första raden innehåller talet $N \ge 1$.

Därefter följer $N$ rader, som vardera innehåller först talet $m_ i \ge 1$, och sedan $m_ i$ heltal $a_{i,j}$, alla mellan 1 och 60.

Output

Du ska skriva ut ett enda tal: den längsta möjliga totala tid du kan få studenterna att stanna om du planerar schemat optimalt.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Summan av alla $m_ i$ kommer att vara högst $5\, 000$ i grupperna 1 till och med 4.

Förklaring

I det givna exemplet ska tre gruppers labbar redovisas: den första gruppens moment tar 5 resp. 15 minuter, den andra 10 resp. 20, och den tredje gruppens moment tar en hel timme.

Om vi lägger redovisningarna i ordningen 5, 10, 60, 20, 15 så kommer den tredje gruppen kunna göra sin redovisning på 60 minuter. Den andra gruppen kommer då att förutom sin egen labb behöva vänta igenom hela den tredjes redovisning, och därmed ta $10+60+20 = 90$ minuter på sig. På samma sätt kommer den första gruppen behöva vänta $5+10+60+20+15 = 110$ minuter. Summan av tiderna blir $60 + 90 + 110 = 260$ minuter.

(Notera att ordningen 10, 15, 60, 20, 5 hade resulterat i en värre tidssumma på $265$, men detta tillåts inte: grupp 1 får inte redovisa sin andra labb före sin första.)

3
2 5 15
2 10 20
1 60

260