Tình hình kinh tế khó khăn trong nước và việc chính phủ cắt giảm trợ cấp nông nghiệp đã khiến Mirko phải thay đổi nghề nghiệp một lần nữa, lần này là làm một tên trộm. Nỗ lực nghề nghiệp đầu tiên của anh ta là một vụ trộm cửa hàng trang sức.

Cửa hàng có ~N~ món trang sức, mỗi món có khối lượng ~M_i~ và giá trị ~V_i~. Mirko có ~K~ túi để đựng chiến lợi phẩm của mình và mỗi túi có thể chứa một lượng ~C_i~ có khối lượng tối đa. Anh ta dự định cất tất cả chiến lợi phẩm của mình trong những chiếc túi này, nhưng nhiều nhất là một món đồ trang sức trong mỗi chiếc túi, để giảm khả năng bị hư hại trong quá trình trốn thoát.

Tìm tổng giá trị trang sức tối đa mà Mirko có thể “giải phóng”.

Input

• Dòng đầu tiên chứa hai số ~N~ và ~K~ ~(1 ≤ N, K \le 300 000)~.
• Mỗi ~N~ dòng tiếp theo chứa một cặp số ~M_i~ và ~V_i~ ~(1 \le M_i, V_i \le 1 000 000)~.
• Mỗi dòng trong ~K~ dòng tiếp theo chứa một số ~C_i~ ~(1 \le C_i \le 100 000 000)~.
• Tất cả các số trong đầu vào đều là số nguyên dương.

Output

• Dòng đầu tiên và duy nhất phải chứa tổng giá trị trang sức tối đa có thể.

Scoring

• Trong dữ liệu kiểm tra có giá trị ít nhất 50% tổng số điểm, ~N~ và ~K~ sẽ nhỏ hơn ~5000~.

Sample Input 1

2 1
5 10
100 100
11

Sample Output 1

10

Sample Input 2

3 2
1 65
5 23
2 99
10
2

Sample Output 2

164

Làm rõ ví dụ thứ hai:

Mirko cất món trang sức đầu tiên vào túi thứ hai và món thứ ba vào túi thứ nhất.