페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5908
서브태스크

전시회 준비 1초 512MB

문제

그림 전시회를 앞두고 전시할 작품을 고르려고 한다. 전시회에서는 각 작품을 액자에 넣어 일렬로 전시할 예정이다.

N개의 후보 작품이 1부터 N으로 번호가 붙어있다. 이때, i번째 작품의 크기는 S_i이고, 값어치는 V_i이다.

또한 M개의 액자들이 1부터 M으로 번호가 붙어있다. 이때, j번째 작품의 크기는 C_j이며, 각 액자에는 크기가 C_j 이하인 작품만이 들어갈 수 있으며, 오직 하나의 작품만이 들어갈 수 있다.

모든 그림은 액자에 넣어야만 전시가 가능한데, 아래와 같은 두 조건을 충족해야만 한다.

  • 이웃한 두 그림에 대해, 오른쪽 그림의 액자 크기는 왼쪽 그림의 액자 크기 이상이어야 한다.

  • 이웃한 두 그림에 대해, 오른쪽 그림의 값어치는 왼쪽 그림의 값어치 이상이어야 한다.

최대한 많은 그림을 전시하려고 한다면, 최대 몇 개의 그림까지 전시가 가능한지 알아보자.


입력

아래와 같은 형식으로 입력이 주어진다.

N M

S_1 V_1

\vdots

S_N V_N

C_1

\vdots

C_M

[제한]

1 ≤ N ≤ 100\,000.

1 ≤ M ≤ 100\,000.

1 ≤ S_i ≤ 1\,000\,000\,000 (1 ≤ i ≤ N).

1 ≤ V_i ≤ 1\,000\,000\,000 (1≤ i ≤ N).

1 ≤ C_j ≤ 1\,000\,000\,000 (1 ≤ j ≤ M).


부분문제

번호 점수 조건
#110점

N ≤ 10, M ≤ 10

#240점

N ≤ 1\,000, M ≤ 1\,000

#350점

추가 제한 없음


예제1

입력
3 4
10 20
5 1
3 5
4
6
10
4
출력
2

(그림2, 액자2), (그림1,액자3)의 경우와 같이 최대 두 개의 그림 전시가 가능하다.


예제2

입력
3 2
1 2
1 2
1 2
1
1
출력
2

예제3

입력
4 2
28 1
8 8
6 10
16 9
4
3
출력
0

예제4

입력
8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543
출력
3

출처

JOI 2019

역링크 공식 문제집만