만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

사랑의 큐피드

면접 대비

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

요약
여학생과 남학생의 키와 선호 기준이 주어질 때, 서로 선호하는 짝을 최대 몇 쌍 만들 수 있는지 구합니다.
난이도

보통10점 중 4점

유형
그래프, DFS
정답자
아직 제출이 없습니다

문제

진주 나들이를 온 보선이는 목이 너무 말라서 경상국립대 앞의 한 카페에 들어갔다. 그 카페에서는 진주교육대 여학생 NN명과 연암공과대 남학생 MM명이 미팅을 하고 있었다.

이 미팅에는 신기한 점이 하나 있다. 학생들이 상대에게 호감을 갖는지는 키 한 가지에만 따라 정해진다. 구체적으로, 여학생은 자신의 선호 기준보다 키가 작은 남학생만 선호한다. 남학생은 자신의 선호 기준보다 키가 큰 여학생만 선호한다.

자칭 사랑의 큐피드 재혁이도 이 카페에 있었다. 재혁이는 미팅 중인 테이블의 대화를 엿들어 모든 학생의 선호 기준을 파악했다. 그리고 많은 커플이 생기기를 바라며 학생들을 직접 이어 주기로 했다.

이 모든 상황을 지켜보던 보선이는 이 미팅에서 생길 수 있는 커플의 최대 수가 궁금해졌다. 이 문제에서 커플은 서로 선호하는 여학생 1명과 남학생 1명으로 이루어진 집합이며, 한 학생은 둘 이상의 커플에 속할 수 없다.

입력

첫 번째 줄에 여학생의 수 NN과 남학생의 수 MM이 공백으로 구분되어 주어진다. (1≤N,M≤4001 \le N, M \le 400)

두 번째 줄에 G1,…,GNG_1, \dots, G_N이 공백으로 구분되어 주어진다. GiG_i는 ii번째 여학생의 키다. (1≤Gi≤3001 \le G_i \le 300)

세 번째 줄에 B1,…,BMB_1, \dots, B_M이 공백으로 구분되어 주어진다. BiB_i는 ii번째 남학생의 키다. (1≤Bi≤3001 \le B_i \le 300)

네 번째 줄에 L1,…,LNL_1, \dots, L_N이 공백으로 구분되어 주어진다. LiL_i는 ii번째 여학생의 선호 기준이다. (1≤Li≤3001 \le L_i \le 300)

다섯 번째 줄에 U1,…,UMU_1, \dots, U_M이 공백으로 구분되어 주어진다. UiU_i는 ii번째 남학생의 선호 기준이다. (1≤Ui≤3001 \le U_i \le 300)

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 미팅에서 생길 수 있는 커플의 최대 수를 출력한다.

예제1

  1. 예제 1

    입력
    2 2
    168 164
    179 183
    180 190
    155 165
    
    예상 출력
    1