Bạn dự định tổ chức một triển lãm tranh. Trong triển lãm, bạn sẽ đặt một số bức tranh vào khung rồi trưng bày chúng thành một hàng.

Có \(N\) bức tranh có thể được chọn, đánh số từ \(1\) đến \(N\). Bức tranh \(i\) có kích thước \(S_i\) và giá trị \(V_i\). Có \(M\) khung tranh, đánh số từ \(1\) đến \(M\). Khung \(j\) có kích thước \(C_j\) và chỉ chứa được tranh có kích thước không vượt quá \(C_j\). Mỗi khung chứa nhiều nhất một bức tranh.

Mỗi bức tranh được trưng bày phải được đặt trong một khung. Để triển lãm trông đẹp mắt, cách sắp xếp phải thỏa mãn:

• Với hai bức tranh bất kỳ đứng cạnh nhau, kích thước khung của bức bên phải không nhỏ hơn kích thước khung của bức bên trái.
• Với hai bức tranh bất kỳ đứng cạnh nhau, giá trị của bức bên phải không nhỏ hơn giá trị của bức bên trái.

Hãy tính số bức tranh lớn nhất có thể trưng bày.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

N M
S_1 V_1
...
S_N V_N
C_1
...
C_M

Dữ liệu ra

In ra một dòng chứa số bức tranh lớn nhất có thể trưng bày.

Ràng buộc

• Các giá trị đầu vào đều là số nguyên.
• \(1 \le N,M \le 100000\).
• \(1 \le S_i,V_i \le 10^9\) với \(1 \le i \le N\).
• \(1 \le C_j \le 10^9\) với \(1 \le j \le M\).

Phân nhóm

Các ràng buộc chung ở trên áp dụng cho mọi nhóm.

1. \(10\) điểm: \(1 \le N,M \le 10\).
2. \(40\) điểm: \(1 \le N,M \le 1000\).
3. \(50\) điểm: \(1 \le N,M \le 100000\).

Ví dụ

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

2

3 2
1 2
1 2
1 2
1
1

2

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

0

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

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 2. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.