벌점을 나눠서 일 배정하기

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

직원마다 자신이 할 수 있는 일의 목록이 정해져 있다. 한 가지 일은 한 명만 담당하고, 직원 한 명은 원래 자신이 할 수 있는 일 중에서 한 개만 맡는다. 다만 지난달에 벌점을 $X$점 받은 직원은 최대 $X+1$개까지 맡을 수 있다.

직원이 세 명이고 지난달 벌점이 1번 직원 민호 2점, 2번 직원 재필이 1점, 3번 직원 주현이 0점이라면, 민호는 최대 3개, 재필이는 최대 2개, 주현이는 최대 1개를 맡는다.

직원은 자기가 몇 점을 받았는지 모르고, 전 직원이 받은 벌점의 합 $K$만 알려져 있다. 강호는 이 사실을 이용해 벌점 $K$점을 직원들에게 원하는 대로 나눠 주고, 처리하는 일의 개수를 최대로 만들려고 한다. 각 직원이 받는 벌점은 0 이상의 정수이고, 그 합은 정확히 $K$이다.

예를 들어 1번 직원이 1, 2, 3, 4, 5번 일을 할 수 있고, 2번과 3번과 4번 직원은 1번 일만, 5번 직원은 1번과 5번 일을 할 수 있다고 하자. $K$가 2일 때 벌점을 1번 직원과 5번 직원에게 1점씩 나눠 주면 네 개까지 처리한다. 대신 2점을 모두 1번 직원에게 몰아주면 1번 직원이 최대 세 개를 맡으므로, 1번 직원이 2, 3, 4번 일을, 2번 직원이 1번 일을, 5번 직원이 5번 일을 맡아 다섯 개를 모두 처리한다.

각 직원이 할 수 있는 일의 목록과 벌점의 합 $K$가 주어졌을 때, $M$개의 일 중 최대 몇 개를 처리할 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 직원의 수 $N$, 일의 개수 $M$, 지난달 벌점의 합 $K$가 공백으로 구분되어 주어진다. ($1 \le N, M \le 1000$, $1 \le K \le N$)

둘째 줄부터 $N$개의 줄에 걸쳐 각 직원이 할 수 있는 일이 주어진다. $i$번째 줄에는 $i$번 직원이 할 수 있는 일의 개수와 그 일의 번호가 공백으로 구분되어 주어진다. 일의 개수는 0 이상 $M$ 이하이고, 한 줄에 같은 번호가 두 번 나오지 않는다.

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