Exhibition

Time limit1sMemory limit512 MB

Summary

Choose the largest set of pictures and assign each to a distinct frame so that the sequence is nondecreasing in both assigned frame size and picture value.

Level: Medium7 of 10
Topics: Sorting, Greedy, Binary search, Dynamic programming
Solved: No attempts yet

Problem

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.

Input

Read the following data from the standard input.

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

Output

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

Constraints

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

Examples4

Example 1
Input
```
3 4
10 20
5 1
3 5
4
6
10
4
```
Expected output
```
2
```
Example 2
Input
```
3 2
1 2
1 2
1 2
1
1
```
Expected output
```
2
```
Example 3
Input
```
4 2
28 1
8 8
6 10
16 9
4
3
```
Expected output
```
0
```

Example 4

Input

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

Expected output