여행사

바이트랜드 주민들이 예전보다 훨씬 자주 여행을 다니기 시작했습니다. 사업 수완이 좋은 바이트맨은 여행사를 차리기로 했습니다. 개업 첫날 $n$명의 손님이 여행사를 찾아왔고(이들을 $1$부터 $n$까지의 정수로 구분합니다), 모두 여행을 떠나고 싶어 합니다. 하지만 손님마다 각자의 조건이 있습니다.

바이트맨의 이익이 최대가 되도록 여행에 데려갈 손님들을 골라 주세요.

각 손님은 자신에게 이 여행이 얼마만큼의 가치가 있는지 바이트맨에게 알려 주었습니다. $i$번째 손님에게 여행의 가치를 $x_i$라 합시다 ($-1\,000\,000 \le x_i \le 1\,000\,000$). $x_i \ge 0$이면 이 손님은 여행 대금으로 $x_i$ 데빌라를 지불하고, $x_i < 0$이면 이 손님이 여행을 가는 경우 바이트맨이 그 손님에게 $-x_i$ 데빌라를 지불해야 합니다.

금전적인 조건 외에 손님에게는 사회적인 조건도 있습니다. $i$번째 손님에게는 $k_i$개의 조건이 있고 ($0 \le k_i \le n-1$), 그중 $j$번째 조건은 정수 쌍 $(a_{ij}, b_{ij})$로 나타냅니다 ($1 \le a_{ij} \le n$, $a_{ij} \ne i$, $1 \le b_{ij} \le 1\,000\,000$). 이 조건의 의미는, $i$번째 손님이 여행을 가면 $a_{ij}$번째 손님도 반드시 여행을 가거나, 그렇지 않으면 $i$번째 손님의 여행 대금을 $b_{ij}$ 데빌라만큼 깎아 주어야 한다는 것입니다 (이 때문에 어떤 손님의 대금이 양수에서 음수로 바뀌어, 사회적 조건이 일부 충족되지 않은 채로 여행을 가는 손님에게 바이트맨이 오히려 돈을 지불하게 될 수도 있습니다).

여행에 데려갈 수 있는 손님 수에는 제한이 없습니다. 바이트맨의 이익은 여행을 가는 손님들의 대금 합계에서, 충족되지 못한 사회적 조건마다 깎아 준 금액 $b_{ij}$를 뺀 값입니다. 이 이익을 최대로 만들어 주세요.

첫째 줄에 여행사를 찾아온 손님 수를 나타내는 정수 $n$이 주어집니다 ($1 \le n \le 1\,000$). 이어지는 $n$개의 줄이 손님들을 설명합니다. $i+1$번째 줄 ($1 \le i \le n$)에는 정수 $x_i$ ($-1\,000\,000 \le x_i \le 1\,000\,000$)와 $k_i$ ($0 \le k_i \le n-1$)가 주어지고, 그 뒤에 $k_i$개의 정수 쌍 $(a_{ij}, b_{ij})$가 주어집니다 ($1 \le a_{ij} \le n$, $a_{ij} \ne i$, $1 \le b_{ij} \le 1\,000\,000$). 한 줄의 모든 수는 공백 하나로 구분됩니다. 한 손님이 다른 특정 손님 한 명에 대해 갖는 사회적 조건은 많아야 하나임이 보장됩니다.

바이트맨이 얻을 수 있는 최대 이익을 정수 하나로 출력하세요. 아무도 데려가지 않으면 이익은 $0$이므로, 답은 항상 $0$ 이상입니다.