지원실의 임시 저장 장치

문제

사내 IT 지원실에서는 작업 공간이 부족한 직원에게 임시 저장 장치를 빌려준다. 이번 대여 기간에는 장치를 중간에 반납하거나 다른 직원에게 넘길 수 없다. 지원실은 지금 보관 중인 장치만 사용하여 가능한 한 많은 직원의 요청을 처리하려 한다. 직원마다 처리되는 요청 하나의 중요도는 같으며, 요청한 용량이 크다는 이유로 더 높은 점수를 주지는 않는다. 직원의 요청에는 필요한 최소 저장 용량이 적혀 있다. 어떤 장치의 용량이 그 값 이상이면 그 장치를 해당 직원에게 배정할 수 있다. 장치의 용량과 필요한 최소 용량이 정확히 같아도 배정할 수 있다. 더 큰 장치를 배정했을 때 남는 용량은 사용하지 않은 채로 두며, 그 남는 부분을 다른 직원에게 나누어 줄 수 없다. 각 직원에게는 장치를 최대 하나만 배정할 수 있고, 각 장치도 직원 한 명에게만 배정할 수 있다. 여러 장치를 합쳐서 한 직원의 최소 용량을 맞추는 것은 허용되지 않는다. 예를 들어 최소 용량이 9인 요청은 용량이 5인 장치 두 개로 처리할 수 없다. 같은 용량의 장치가 여러 개 있다면 각각 별개의 장치로 취급한다. 최소 용량이 같은 요청이 여러 개 있는 경우에도 서로 다른 직원의 요청이다. 지원실은 모든 요청과 보유 장치의 용량을 확인한 뒤 배정을 결정한다. 요청이 입력된 순서대로 처리할 필요는 없으며, 어떤 직원의 요청을 처리하지 않고 남겨 두어도 된다. 배정받는 직원 수가 최대가 되도록 선택했을 때 그 직원 수를 구하려 한다. 최대 인원을 달성하는 배정 방법이 여러 가지여도 실제 배정 내역이나 사용한 장치의 용량 합계는 구하지 않는다. 누구에게도 장치를 배정할 수 없다면 처리 가능한 직원 수는 0이다.

입력

첫째 줄에 요청한 직원 수 N과 보유 장치 수 M이 주어진다. 1 ≤ N ≤ 25,000, 1 ≤ M ≤ 25,000이다.
둘째 줄에 각 직원이 요청한 최소 용량 A_1, A_2, ..., A_N이 주어진다.
셋째 줄에 각 장치의 용량 B_1, B_2, ..., B_M이 주어진다.
모든 용량은 1 이상 999,999 이하의 정수이며, 같은 단위를 사용한다.

출력

조건을 지키면서 장치를 배정받을 수 있는 직원 수의 최댓값을 정수 하나로 출력한다. 배정 가능한 직원이 없으면 0을 출력한다.

5 4
8 3 6 3 10
3 7 4 9

4

3 4
12 12 15
1 5 11 11

0

4 3
5 5 5 5
5 5 5

3

출처: Devin.KR 자체 제작