사탕

토요일이고, Ann Britt-Caroline은 사탕을 사러 간다. 그녀는 구매를 고려 중인 서로 다른 사탕 봉지 여러 개를 골라 두었다.

각 봉지에는 서로 다른 종류의 사탕이 일정 개수씩 들어 있다. 일반 사탕은 $10$종류이며(번호는 $1, \ldots, 10$이다), 반사탕은 $10$종류이다(번호는 $-1, \ldots, -10$이다). 공교롭게도 $n$번 종류의 사탕과 $-n$번 종류의 사탕은 서로 잘 어울리지 않아, 서로 접촉하면 소멸한다. 그 외에는 반사탕의 맛도 일반 사탕과 똑같다.

Ann Britt-Caroline은 사탕 봉지를 산 뒤, 모든 사탕과 반사탕의 쌍이 소멸하도록 큰 그릇에 사탕을 넣고 완전히 섞는다. 사탕 봉지를 최적으로 선택할 때, 모든 사탕과 반사탕의 쌍이 소멸한 후 Ann Britt-Caroline에게 남을 수 있는 사탕은 최대 몇 개인가? 각 종류의 봉지는 하나만 살 수 있다는 점에 유의하라. 돈과 관련된 문제는 무시하라. 부모님이 비용을 지불할 것이다.

채점

제출한 해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트를 통과해야 한다.

그룹  |  점수  |  제한 조건

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

$2$ | $25$ | $N \le 1000$. 각 봉지에는 한 종류의 사탕만 들어 있다.

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

입력의 첫째 줄에는 사탕 봉지의 수를 나타내는 정수 $1 \le N \le 1000$이 주어진다.

이어지는 $n$개의 줄은 각 사탕 봉지를 설명한다. 각 줄은 봉지에 들어 있는 서로 다른 사탕 종류의 수를 나타내는 정수 $1 \le k \le 10$로 시작한다. 그다음에는 정수 쌍 $s$ $n$이 $k$개 주어지며, 이는 $s$번 종류의 사탕이 $n$개 있다는 뜻이다. 각 사탕 종류는 봉지마다 최대 한 번 언급되며, $s$번 종류와 $-s$번 종류는 같은 봉지에 들어 있을 수 없다.

모든 $n$에 대해, $1 \le n \le 1000$이다.

마지막에 Ann Britt-Caroline이 가질 수 있는 사탕의 최대 개수를 나타내는 정수를 출력한다.

Ann Britt-Caroline은 처음 두 봉지를 사면 가장 많은 사탕을 얻게 된다. 그러면 $1$번 종류의 사탕 하나와 $-1$번 종류의 사탕 하나가 소멸하고, $1$번 종류의 사탕 두 개와 $-2$번 종류의 사탕 다섯 개가 남는다.