시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

N(3≤N≤200)명의 사람이 파티를 하려고 한다. 각각의 사람은 몇 종류의 음식을 요리할 줄 안다. 각각의 음식의 종류는 1부터 D(;5≤D≤100)까지의 정수로 표현된다 하자. 파티를 위해서 각각의 사람이 요리를 해서 가져오기로 했는데, 가급적이면 많은 양(접시의 수로 계산)의 음식을 파티에 준비하려 한다.

그렇다면 각각의 음식을 최대한 많이 준비해 오면 되겠지만, 우선 각각의 사람이 가져올 수 있는 음식의 양에 제한이 있다. 각각의 사람은 최대 K(1≤K≤5)개의 접시밖에 가져올 수 없다고 하자. 이 때 같은 종류의 음식은 한 접시밖에 가져갈 수 없다고 하자. 즉, 한 사람이 세 접시의 스테이크를 가져올 수 없지만, 한 접시의 스테이크, 한 접시의 샐러드, 한 접시의 파스타를 가져올 수 있다.

또한 각 음식의 종류마다도 가져올 수 있는 양에 제한이 있다. 예를 들어 소스 같은 경우에는 적은 개수의 접시만 있더라도 충분하지만, 샐러드 같은 경우에는 많은 개수의 접시가 있어야 한다.

이와 같은 제한들이 주어졌을 때, 파티에 준비될 수 있는 접시(물론 음식이 담겨있는)의 개수의 최대값을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 다음 N개의 줄에는 각 사람이 요리할 줄 아는 음식의 종류 개수 Z(1≤Z≤D)와, Z개의 정수로 요리할 줄 아는 음식의 번호가 주어진다.

출력

첫째 줄에 파티에 준비될 수 있는 접시 개수의 최대값을 출력한다.

예제 입력

4 3 5
2 2 2 2 3
4 1 2 3 4
4 2 3 4 5
3 1 2 4
3 1 2 3

예제 출력

9

힌트