시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 61 21 14 43.750%

문제

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

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

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

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

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

입력

첫째 줄에 도시의 개수 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번 도시부터 차례대로 주어진다.

출력

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

예제 입력

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

예제 출력

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번 일어난다.

출처

  • 빠진 조건을 찾은 사람: ainta
  • 문제를 번역한 사람: baekjoon