일 배정 3

시간 제한3초메모리 제한256 MB

요약

각 직원이 가능한 일 목록 안에서 일을 맡고 K명은 최대 두 일을 맡아 끝낼 수 있는 일 수를 구합니다.

문제

강호네 회사에는 직원이 $N$ 명 있고, 처리해야 할 일이 $M$ 개 있다. 직원은 1번부터 $N$ 번까지, 일은 1번부터 $M$ 번까지 번호가 매겨져 있다.

각 직원은 자신이 할 수 있는 일 중에서 한 개만 맡고, 하나의 일을 맡는 직원은 한 명이어야 한다. 단, $N$ 명 중에서 $K$ 명은 일을 최대 2개까지 맡을 수 있다.

직원마다 할 수 있는 일의 목록이 주어질 때, $M$ 개의 일 중에서 최대 몇 개를 처리할 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 직원의 수 $N$ , 일의 개수 $M$ , 일을 2개까지 맡을 수 있는 직원의 수 $K$ 가 주어진다. ( $1 \le N, M \le 1000$ , $1 \le K \le N$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 각 직원의 정보가 주어진다. $i$ 번째 줄에는 $i$ 번 직원이 할 수 있는 일의 개수와 그 일의 번호가 차례로 주어진다.

첫째 줄에 강호네 회사에서 처리할 수 있는 일의 최대 개수를 출력한다.

첫 번째 예제에서 1번 직원이 일을 2개 맡으면 1번 직원이 1번과 2번, 2번 직원이 3번, 3번 직원이 5번 일을 맡아 모두 4개를 처리한다.

예제 3

입력

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

예상 출력