페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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

입력
34
1020
51
35
4
6
10
4
출력
2

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


예제2

입력
32
12
12
12
1
1
출력
2

예제3

입력
42
281
88
610
169
4
3
출력
0

예제4

입력
88
50891760435617051
501958939840246141
48533840232896484
957730250357542366
904165504137209882
684085683775621730
55295362920004459
125090903607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543
출력
3

출처

JOI 2019

역링크 공식 문제집만