# Problem K

Candy

Languages
en
sv
It is Saturday and Ann Britt-Caroline is going to buy candy. She has identified several different bags of candy she is considering buying.

Each bag contains a number of pieces of candy of different types. There are $10$ types of normal candy (these are numbered $1, \ldots , 10$), and $10$ types of anti-candy (numbered $-1, \ldots , -10$). It just so happens that candy of type $n$ and type $-n$ do not go well together – they are annihilated if they come in contact with each other. Other than that anti-candy tastes just the same as normal candy.

When Ann Britt-Caroline has bought the bags of candy she mixes them in a big bowl such that all pairs of candy/anti-candy are annihilated (she mixes thoroughly). How many pieces of candy can Ann Britt-Caroline have left (after all pairs of candy/anti-candy are annihilated), if she selects her bags of candy optimally? Note that she can only buy one bag of each type. Ignore any money-related issues – her parents will pay.

## Input

The first line in the input consist of an integer $1 \le N \le 1000$ - the number of bags of candy.

The following $n$ lines describe each bag of candy. Each line starts with an integer $1 \le k \le 10$, specifying the number of different types of candy in the bag. Then follow $k$ pairs of integers $s$ $n$, which means that there are $n$ pieces of candy type $s$. Each type of candy is mentioned at most once per bag, and types $s$ and $-s$ can not be in the same bag.

For all $n$, $1 \le n \le 1000$.

## Output

Print an integer: the largest amount of candy Ann Britt-Caroline can have in the end.

## Grading

Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.

Group |
Points |
Constraints |

$1$ |
$25$ |
$N \le 15$ |

$2$ |
$25$ |
$N \le 1000$. Each bag will contain only one type of candy. |

$3$ |
$50$ |
$N \le 1000$ |

## Explanation of the sample

Ann Britt-Caroline gets the largest amount if she buys the first two bags. Then a candy of type $1$ and one of type $-1$ are eliminated, and two candies of type $1$ remain, and five of type $-2$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 1 3 2 -1 1 -2 5 2 2 2 -3 1 |
7 |