세금 계산

존스 가문은 여러 세대에 걸쳐 한 지역에 살아온 부유한 가문이다. 이 지역의 집은 여기저기 흩어져 있고, 비포장 도로가 집과 집을 잇는다. 비포장 도로 하나로 직접 이어진 두 집을 이웃이라고 부른다. 같은 도로를 두 번 지나지 않으면서 어떤 집에서 다른 어떤 집으로 가는 방법은 정확히 한 가지다.

이 나라에 새 왕이 즉위했고, 왕은 세금을 특이한 방식으로 걷기로 했다.

각 집은 작년 소득의 약수 하나를 고른다. 원한다면 소득 전체를 골라도 된다. 이웃한 두 집이 고른 수의 최대공약수가 1보다 크면, 왕은 이 지역 모든 사람에게서 돈을 전부 빼앗는다. 이웃한 모든 쌍이 고른 수의 최대공약수가 1이면, 각 집은 자기가 고른 금액을 그대로 지킨다.

모든 집이 1달러를 고르는 방법도 있지만 그래서는 남는 것이 거의 없다. 집들이 지키는 금액의 합을 최대로 만들어라.

입력은 테스트 케이스 하나로 이루어진다.

첫째 줄에 집의 수 $n$ ($2 \le n \le 250$)이 주어진다. 다음 $n$개의 줄에 각 집의 정보가 한 줄씩 주어진다. 첫 줄은 집 1, 둘째 줄은 집 2의 정보다.

각 줄은 두 정수 $I_k$ ($1 \le I_k \le 200\,000\,000$)와 $m_k$ ($1 \le m_k \le n-1$)로 시작한다. $I_k$는 집 $k$의 소득이고 $m_k$는 집 $k$의 이웃 수다. 그 뒤에 집 $k$의 이웃 번호 $m_k$개가 주어진다. 이 번호는 서로 다르고, 1 이상 $n$ 이하이며, $k$와 같지 않다.

모든 도로는 양방향이고, 양 끝 집마다 한 번씩 입력에 두 번 나온다.

집들이 지킬 수 있는 금액 합의 최댓값을 정수 하나로 출력한다.