전시회
시간 제한1초메모리 제한512 MB
사진마다 서로 다른 액자를 배정하고, 배정된 액자 크기와 사진 가치가 모두 비감소하도록 배열할 때 전시할 수 있는 사진 수의 최댓값을 구한다.
문제
그림 전시회를 열려고 한다. 전시회에서는 몇 개의 그림을 액자에 넣어 한 줄로 나란히 전시한다.
전시할 후보 그림이 N개 있고, 1번부터 N번까지 번호가 붙어 있다. 그림 i (1 ≤ i ≤ N)의 크기는 Si이고 가치는 Vi이다.
또한 그림을 넣을 액자가 M개 있고, 1번부터 M번까지 번호가 붙어 있다. 액자 j (1 ≤ j ≤ M)의 크기는 Cj이다. 액자 j에는 크기가 Cj 이하인 그림만 넣을 수 있다. 한 액자에는 그림을 최대 한 개만 넣을 수 있다.
전시할 모든 그림은 반드시 액자에 넣어야 한다. 보기 좋게 하기 위해 다음 조건을 만족해야 한다.
- 이웃한 두 그림에 대해, 오른쪽 그림을 넣은 액자의 크기는 왼쪽 그림을 넣은 액자의 크기 이상이어야 한다.
- 이웃한 두 그림에 대해, 오른쪽 그림의 가치는 왼쪽 그림의 가치 이상이어야 한다.
그림을 최대한 많이 전시하려고 한다.
그림의 수, 액자의 수, 그리고 각각의 크기와 가치가 주어졌을 때 전시할 수 있는 그림의 최대 개수를 구하는 프로그램을 작성하시오.
입력
다음 데이터를 표준 입력에서 읽는다.
N M
S1 V1
.
.
.
SN VN
C1
.
.
.
CM
출력
표준 출력에 한 줄을 출력한다. 전시할 수 있는 그림의 최대 개수를 출력해야 한다.
제한
- 1 ≤ N ≤ 100 000.
- 1 ≤ M ≤ 100 000.
- 1 ≤ Si ≤ 1 000 000 000 (1 ≤ i ≤ N).
- 1 ≤ Vi ≤ 1 000 000 000 (1 ≤ i ≤ N).
- 1 ≤ Cj ≤ 1 000 000 000 (1 ≤ j ≤ M).