시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 48 33 28 68.293%

문제

You are going to hold an exhibition of pictures. In the exhibition, you will put some pictures into frames and exhibit them, lining them up in a row.

There are N candidate pictures for the exhibition, numbered from 1 through N. The picture i (1 ≤ i ≤ N) has size Si and value Vi.

Also, there are M frames for the pictures, numbered from 1 through M. The frame j (1 ≤ j ≤ M) has size Cj. Only pictures of size at most Cj can be put into the frame j. At most one picture can be put into a frame.

Every picture to be exhibited must be put into a frame. For the sake of appearance, they must satisfy the following conditions:

  • For any neighboring two pictures, the size of the frame containing the right picture must be at least the size of the frame containing the left picture.
  • For any neighboring two pictures, the value of the right picture must be at least the value of the left picture.

You want to exhibit as many pictures as possible.

Write a program which, given the number of pictures, the number of frames, and their sizes and values, calculates the maximum number of pictures to be exhibited.

입력

Read the following data from the standard input.

N M
S1 V1
.
.
.
SN VN
C1
.
.
.
CM

출력

Write one line to the standard output. The output should contain the maximum number of pictures to be exhibited.

제한

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

예제 입력 1

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

예제 출력 1

2

In this sample, you can exhibit 2 pictures by lining them up as (picture 2, frame 2), (picture 1, frame 3) from left to right. As you cannot exhibit 3 or more pictures, output 2. Here, (picture i, frame j) denotes the picture i put in the frame j.

예제 입력 2

3 2
1 2
1 2
1 2
1
1

예제 출력 2

2

예제 입력 3

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

예제 출력 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

예제 출력 4

3