아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

만찬

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 소가 좋아하는 음식과 음료가 있고 각 항목은 한 마리에게만 줄 수 있을 때, 좋아하는 음식과 음료를 모두 받는 소의 최대 수를 구한다.
난이도

보통10점 중 7점

유형
그래프, 동적 계획법, 비트 연산, 완전 탐색
정답자
아직 제출이 없습니다

문제

소들은 입맛이 까다롭습니다. 각 소는 정해진 음식만 먹고, 정해진 음료만 마십니다.

농부 존은 소들에게 줄 식사를 준비했지만, 메뉴가 소들의 취향에 맞는지 미리 확인하지 못했습니다. 모두를 만족시키지는 못하더라도, 되도록 많은 소에게 음식 하나와 음료 하나로 이루어진 완전한 식사를 주고 싶습니다.

농부 존은 FF가지 음식과 DD가지 음료를 준비했습니다 (1≤F,D≤1001 \le F, D \le 100). NN마리의 소 (1≤N≤1001 \le N \le 100)는 각자 자신이 먹을 음식과 마실 음료를 정해 두었습니다. 각 소에게 음식 한 종류와 음료 한 종류를 배정하여, 음식과 음료를 모두 받는 소의 수를 최대로 만드세요.

각 음식과 각 음료는 한 마리의 소에게만 줄 수 있습니다 (예를 들어 음식 2번을 어떤 소에게 배정하면, 다른 소에게는 음식 2번을 배정할 수 없습니다). 또한 각 소는 음식 한 종류와 음료 한 종류만 받을 수 있습니다.

입력

  • 첫째 줄: 공백으로 구분된 세 정수 NN, FF, DD.
  • 둘째 줄부터 N+1N+1째 줄까지: i+1i+1째 줄은 소 ii를 설명합니다. 먼저 두 정수 FiF_i와 DiD_i가 주어지며, 각각 소 ii가 좋아하는 음식의 수와 음료의 수입니다. 이어지는 FiF_i개의 정수는 소 ii가 먹을 음식이고, 그 다음 DiD_i개의 정수는 소 ii가 마실 음료입니다.

출력

  • 정수 하나: 자신이 원하는 음식과 음료를 모두 받을 수 있는 소의 최대 수.

예제1

  1. 예제 1

    입력
    4 3 3
    2 2 1 2 3 1
    2 2 2 3 1 2
    2 2 1 3 1 2
    2 1 1 3 3
    
    예상 출력
    3