떡국

떡국의 왕 도현이는 나라의 각 도시를 지키기 위해 경비를 더 고용하려고 한다. 떡국에는 K개의 경비업체가 있고, 각 업체는 일부 도시에만 사무실을 가지고 있다.

업체 B의 경비를 도시 A에 새로 배치하려면, 업체 B가 도시 A에 사무실을 가지고 있어야 한다. 이미 배치된 경비는 옮기거나 해고할 수 없지만, 이 조건을 지키는 한 새 경비는 원하는 만큼 고용할 수 있다.

두 도시가 협력 관계일 때, 어떤 업체의 경비가 한쪽 도시에만 있고 다른 쪽 도시에는 없으면 그 업체 하나가 하나의 충돌을 만든다. 한 도시에는 여러 업체의 경비가 있을 수 있으므로, 같은 도시 쌍에서도 여러 충돌이 생길 수 있다.

협력 관계, 이미 배치된 경비의 업체, 각 도시의 업체 사무실 정보가 주어진다. 경비를 추가로 배치해서 만들 수 있는 충돌 수의 최솟값을 구하라.

첫째 줄에 도시의 수 N이 주어진다. (1 <= N <= 50)

다음 N개의 줄에는 도시들의 협력 관계가 인접행렬로 주어진다. 0은 협력하지 않는 관계, 1은 협력하는 관계를 뜻한다. 인접행렬을 A라고 하면 A[i][i] = 0이고 A[i][j] = A[j][i]이다.

그다음 줄에 경비업체의 수 K가 주어진다. (1 <= K <= 50)

이어지는 N개의 줄에는 0번 도시부터 차례대로, 이미 그 도시에 배치된 경비의 수와 각 경비의 업체 번호가 주어진다. 업체 번호는 0부터 시작한다.

마지막 N개의 줄에는 0번 도시부터 차례대로, 그 도시에 사무실을 둔 경비업체의 수와 업체 번호가 주어진다.

경비를 추가로 배치해서 만들 수 있는 충돌 수의 최솟값을 출력한다.

각 업체는 서로 독립적으로 생각할 수 있다. 한 업체에 대해 이미 경비가 있는 도시는 반드시 선택되고, 사무실이 없고 기존 경비도 없는 도시는 선택할 수 없다. 협력 관계의 양 끝 중 정확히 한쪽만 선택된 간선 수를 최소화하면 된다.

첫 번째 공개 테스트에서는 1번과 3번 도시에 0번 업체 경비를 추가하면 도시 0과 2 사이에서만 충돌이 남는다. 네 번째 공개 테스트의 최소 충돌 수는 7이다.