Godis
Det är lördag, och Ann Britt-Caroline ska handla godis. Hon har identifierat ett antal olika godispåsar hon kan tänka sig att köpa.
Varje påse innehåller ett antal godisbitar av olika sorter. Det finns 10 olika sorters vanligt godis (dessa är numrerade $1...10$), och 10 sorter av en ny typ av anti-godis (numrerade $-1...-10$). Det händer sig nu att godisbitar av sort $n$ och av sort $-n$ inte går särskilt väl ihop - de annihileras när de kommer i kontakt med varandra. I övrigt har dock anti-godiset samma konsistens och smak som vanligt godis.
När Ann Britt-Caroline köpt alla godispåsar hon vill ha så blandar hon ihop påsarna i en stor skål, så att samtliga par av godis/anti-godisar tar ut varandra (hon blandar godisskålen grundligt). Hur många godisbitar kan Ann Britt-Caroline ha kvar i slutet (efter att godis/anti-godis tagit ut varandra), om hon väljer godispåsar på bästa sätt? Observera att hon bara kan köpa en enda godispåse av varje sort. Ignorera eventuella pengabekymmer - hennes föräldrar bjuder.
Input
Den första raden i indatan innehåller ett heltal $1 \le N \le 1000$ - antalet godispåsar.
De följande $N$ raderna beskriver varje godispåse. Först på raden finns ett tal $1 \le k \le 10$, som specificerar antalet olika sorters godis i påsen. Sedan följer $k$ par av tal $s$ $n$, vilket betyder att det finns $n$ godisar av sort $s$. Varje sort nämns högst en gång per godispåse, och sorterna $s$ och $-s$ kan av naturliga skäl inte förekomma tillsammans i samma påse.
Alla $n$ kommer att uppfylla $1 \le n \le 1000$.
Output
Skriv ut ett tal: den största mängden godis Ann Britt-Caroline kan ha i slutändan.
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.
|
Grupp |
Poängvärde |
Begränsningar |
|
1 |
25 |
$N \le 15$ |
|
2 |
25 |
$N \le 1000$. Varje påse innehåller bara en sorts godis. |
|
3 |
50 |
$N \le 1000$ |
Förklaring till exemplet
Den största mängden får Ann Britt-Caroline om hon köper de två första påsarna. Då kommer en godis av sort 1 och en godis av sort -1 elimineras, och kvar blir två godisar kvar av sort 1, och fem av sort -2.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 1 3 2 -1 1 -2 5 2 2 2 -3 1 |
7 |
