¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#5908
Subtarea

전시회 준비 1s 512MB

Problemas

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

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

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

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

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

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

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


Entrada

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

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).


Subtarea

# Puntaje Condición
#110

N ≤ 10, M ≤ 10

#240

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

#350

추가 제한 없음


Ejemplo #1

3 4
10 20
5 1
3 5
4
6
10
4
2

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


Ejemplo #2

3 2
1 2
1 2
1 2
1
1
2

Ejemplo #3

4 2
28 1
8 8
6 10
16 9
4
3
0

Ejemplo #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

Fuente

JOI 2019

Debes iniciar sesión para escribir código.