16981번 - Exhibition 서브태스크다국어

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 S_i and value V_i.

Also, there are M frames for the pictures, numbered from 1 through M. The frame j (1 ≤ j ≤ M) has size C_j. Only pictures of size at most C_j 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 ≤ 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).