만찬
면접 대비시간 제한1초메모리 제한128 MB
각 소가 좋아하는 음식과 음료가 있고 각 항목은 한 마리에게만 줄 수 있을 때, 좋아하는 음식과 음료를 모두 받는 소의 최대 수를 구한다.
문제
소들은 입맛이 까다롭습니다. 각 소는 정해진 음식만 먹고, 정해진 음료만 마십니다.
농부 존은 소들에게 줄 식사를 준비했지만, 메뉴가 소들의 취향에 맞는지 미리 확인하지 못했습니다. 모두를 만족시키지는 못하더라도, 되도록 많은 소에게 음식 하나와 음료 하나로 이루어진 완전한 식사를 주고 싶습니다.
농부 존은 가지 음식과 가지 음료를 준비했습니다 (). 마리의 소 ()는 각자 자신이 먹을 음식과 마실 음료를 정해 두었습니다. 각 소에게 음식 한 종류와 음료 한 종류를 배정하여, 음식과 음료를 모두 받는 소의 수를 최대로 만드세요.
각 음식과 각 음료는 한 마리의 소에게만 줄 수 있습니다 (예를 들어 음식 2번을 어떤 소에게 배정하면, 다른 소에게는 음식 2번을 배정할 수 없습니다). 또한 각 소는 음식 한 종류와 음료 한 종류만 받을 수 있습니다.
입력
- 첫째 줄: 공백으로 구분된 세 정수 , , .
- 둘째 줄부터 째 줄까지: 째 줄은 소 를 설명합니다. 먼저 두 정수 와 가 주어지며, 각각 소 가 좋아하는 음식의 수와 음료의 수입니다. 이어지는 개의 정수는 소 가 먹을 음식이고, 그 다음 개의 정수는 소 가 마실 음료입니다.
출력
- 정수 하나: 자신이 원하는 음식과 음료를 모두 받을 수 있는 소의 최대 수.