시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB160675156.044%

문제

떡국의 왕 도현이는 나라를 지키기 위해 각각의 도시에 경비를 뽑으려고 한다. 떡국에는 총 K개의 서로 다른 경비업체가 있으며, 각 경비업체는 일부 도시들에 사무실을 가지고 있다.

어떤 도시 A에서 경비업체 B가 일을 하려면, B는 A에 사무실이 있어야 한다. 이런 경우에 B는 A에 한 명의 경비를 일하게 할 수 있다. 사무실이 없는 경우에는 그 도시에 경비를 둘 수 없다.

도현이는 위의 규칙을 지키는 동안에는 원하는 만큼 경비를 고용할 수 있다. 하지만, 이미 있는 경비를 이동시키거나 해고시킬수는 없다.

도시 간에는 협력하는 관계가 있을 수 있다. 도시 A와 도시 B가 협력하는 관계이고, 경비업체 C의 경비가 A에서 일하는데, B에서는 경비업체 C의 경비가 없는 경우가 있다. 이런 경우를 충돌이라고 한다. 충돌의 개수는 모든 협력하는 도시의 쌍에서 존재하는 충돌의 개수이다. 한 도시에서 일하는 경비업체는 여러 개일 수 있기 때문에, 한 도시의 쌍에서 존재하는 충돌의 개수는 여러 개일 수도 있다.

협력하는 도시의 쌍과, 각 도시에 이미 있는 경비의 회사 이름, 경비업체의 사무실이 주어졌을 때, 경비를 적절히 뽑아 충돌의 개수를 최소로 하는 프로그램을 작성하시오.

입력

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

둘째 줄에는 협력하는 도시의 관계가 인접행렬 형식으로 주어진다. 0은 협력하지 않는 관계를 나타내고, 1은 협력하는 관계를 나타낸다. 인접행렬을 A라고 했을 때, A[i][i] = 0, A[i][j] = A[j][i]를 만족한다.

다음 줄에는 떡국에 존재하는 경비업체의 수 K (1 ≤ K ≤ 50)가 주어진다. 다음 줄부터 N개의 줄에는 각 도시에 이미 있는 경비의 수와 경비업체의 번호가 0번 도시부터 차례대로 주어진다. 경비업체의 번호는 0부터 시작한다.

다음 줄부터 N개의 줄에는 각 도시에 있는 경비업체 사무실의 개수와 사무실을 가지고 있는 경비업체의 번호가 0번 도시부터 차례대로 주어진다.

출력

첫째 줄에 경비를 적절히 뽑아 만들 수 있는 충돌의 최솟값을 출력한다.

예제 입력 1

4
0111
1000
1000
1000
1
1 0
0
0
0
1 0
1 0
0
1 0

예제 출력 1

1

예제 입력 2

3
011
101
110
1
1 0
0
0
1 0
0
0

예제 출력 2

2

예제 입력 3

3
011
101
110
1
0
0
0
1 0
1 0
1 0

예제 출력 3

0

예제 입력 4

6
010100
101100
010011
110010
001100
001000
3
2 1 2
0
1 1
0
1 0
1 0
3 0 1 2
2 0 1
3 0 1 2
2 1 2
1 0
1 0

예제 출력 4

7

힌트

예제 1의 경우에 떡국에는 경비업체가 1개 있다. 1번과 3번에 경비를 고용하면, 도시 0과 2사이에서만 충돌이 일어나고 이 값이 최솟값이 된다.

예제 2의 경우에는 더 고용할 수 있는 경비가 없다. 따라서, 충돌은 2이다.

예제 3의 경우에는 모든 도시에 경비를 고용하거나, 경비를 전혀 고용하지 않는 방법이 있다. 이때의 충돌은 0이다.

예제 4의 경우에 경비업체의 수는 3이다. 2번 도시에 0번 경비업체의 경비를 고용하고, 1번과 3번도시에는 1번 경비업체를 고용하면 충돌은 7이고, 이 값이 최소이다. 충돌은 3과 4에서 2번, 0과 1, 0과 3, 1과 2, 2와 4, 2와 5에서 1번 일어난다.

출처

  • 문제의 오타를 찾은 사람: adh0463
  • 빠진 조건을 찾은 사람: ainta
  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: kcm1700