사랑의 큐피드

면접 대비

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

요약
여학생과 남학생의 키와 선호 기준이 주어질 때, 서로 선호하는 짝의 최대 개수를 구한다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 투 포인터
정답자
아직 제출이 없습니다

문제

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

이 미팅에는 신기한 사실이 하나 있는데, 바로 미팅 중인 학생들의 상대에 대한 선호 여부는 키라는 요소 한 가지에만 영향을 받는다는 것이다. 구체적으로, 여학생들은 자신의 선호 기준보다 키가 작은 남학생만을 선호한다. 그리고 남학생들은 자신의 선호 기준보다 키가 큰 여학생만을 선호한다.

마침 이 카페에는 자칭 사랑의 큐피드 재혁이도 있었다. 이 미팅에 관심이 생긴 재혁이는 미팅 중인 테이블에서 오가는 얘기를 열심히 엿들어 미팅 중인 모든 학생들의 선호 기준을 파악했다. 그리고 재혁이는 자칭 사랑의 큐피드인 만큼 이 미팅에서 많은 커플이 생겼으면 하는 마음에 학생들을 직접 이어 주기로 결정했다.

이 모든 상황을 흥미롭게 바라보고 있던 보선이는 이 미팅에서 생길 수 있는 커플의 최대 수가 궁금해졌다. 이를 우리가 함께 알아보자. 이 문제에서의 커플은 서로 선호하는 여학생 1명과 남학생 1명으로 이루어진 집합을 의미하며, 한 학생이 둘 이상의 커플에 속할 수 없다.

입력

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

두 번째 줄에는 G_1G\_1, …\dots, G_NG\_N이 공백으로 구분되어 주어진다. G_iG\_i는 ii번째 여학생의 키를 나타낸다. (1≤G_i≤300)(1 ≤ G\_i ≤ 300)

세 번째 줄에는 B_1B\_1, …\dots, B_MB\_M이 공백으로 구분되어 주어진다. B_iB\_i는 ii번째 남학생의 키를 나타낸다. (1≤B_i≤300)(1 ≤ B\_i ≤ 300)

네 번째 줄에는 L_1L\_1, …\dots, L_NL\_N이 공백으로 구분되어 주어진다. L_iL\_i는 ii번째 여학생의 선호 기준을 나타낸다. (1≤L_i≤300)(1 ≤ L\_i ≤ 300)

다섯 번째 줄에는 U_1U\_1, …\dots, U_MU\_M이 공백으로 구분되어 주어진다. U_iU\_i는 ii번째 남학생의 선호 기준을 나타낸다.(1≤U_i≤300)(1 ≤ U\_i ≤ 300)

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

출력

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

예제1

  1. 예제 1

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