영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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, …, 10), and 10 types of anti-candy (numbered -1, …, -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 ≤ N ≤ 1000 - the number of bags of candy.
The following n lines describe each bag of candy. Each line starts with an integer 1 ≤ k ≤ 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 ≤ n ≤ 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 ≤ 15 |
| 2 | 25 | N ≤ 1000. Each bag will contain only one type of candy. |
| 3 | 50 | N ≤ 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.
예제
예제 1
3 1 1 3 2 -1 1 -2 5 2 2 2 -3 1
7