파티
시간 제한2초메모리 제한128 MB
각 요리사가 K개까지 알고 있는 음식을 만들 수 있고 음식별 최대 준비량 제한이 있을 때, 최대 유량으로 준비 가능한 최대 총 접시 수를 구하는 문제입니다.
문제
N명의 사람이 파티에 음식을 가져오려고 한다. 음식 종류는 1번부터 D번까지 번호가 매겨져 있다. 각 사람은 자신이 만들 줄 아는 음식 중에서만 가져올 수 있으며, 한 사람이 가져올 수 있는 접시는 최대 K개이다. 같은 사람이 같은 종류의 음식을 두 접시 이상 가져올 수는 없다.
각 음식 종류마다 준비할 수 있는 접시 수의 상한도 정해져 있다. 주어진 모든 제한을 만족하면서 파티에 준비할 수 있는 접시 수의 최댓값을 구하시오.
입력
첫째 줄에 사람 수 N, 한 사람이 가져올 수 있는 최대 접시 수 K, 음식 종류 수 D가 주어진다 (3 <= N <= 200, 1 <= K <= 5, 5 <= D <= 100).
둘째 줄에는 D개의 정수가 주어진다. i번째 정수는 i번 음식의 최대 접시 수를 뜻한다. 각 값은 0 이상 N 이하이다.
다음 N개의 줄에는 각 사람이 만들 줄 아는 음식 정보가 주어진다. 각 줄은 정수 Z(1 <= Z <= D)로 시작하고, 이어서 그 사람이 만들 줄 아는 음식 번호 Z개가 주어진다.
출력
첫째 줄에 준비할 수 있는 접시 수의 최댓값을 출력한다.