Incredible Okashi Inc. là công ty sản xuất những món bánh kẹo ngon đến khó tin, gọi tắt là công ty IOI. Công ty vừa làm ra những chiếc bánh manju IOI đặc biệt và quyết định đem bán. Có \(M\) loại bánh, mỗi loại được làm đúng một chiếc. Tất cả \(M\) chiếc bánh đều có cùng kích thước, nhưng mỗi chiếc có một hương vị khác nhau nên giá bán cũng khác nhau. Chiếc bánh thứ \(i\) (\(1 \le i \le M\)) có giá \(P_i\) yên.

Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra những phát minh kỳ lạ; ta gọi tắt là công ty JOI. Công ty IOI quyết định đặt mua những chiếc hộp cao cấp của JOI để đựng bánh. JOI sản xuất \(N\) loại hộp đựng bánh manju. Hộp thứ \(j\) (\(1 \le j \le N\)) đựng được tối đa \(C_j\) chiếc bánh và có giá \(E_j\) yên.

IOI sẽ chọn một số loại hộp trong \(N\) loại, có thể chọn từ \(0\) đến \(N\) loại, và đặt mua đúng một hộp thuộc mỗi loại đã chọn. Sau đó, công ty chia bánh vào các hộp để bán thành từng bộ. Giá bán của một bộ bằng tổng giá của những chiếc bánh có trong bộ đó.

Giả sử tất cả các bộ bánh đều bán được, lợi nhuận lớn nhất mà IOI có thể thu được là bao nhiêu? Lợi nhuận bằng tổng giá bán các bộ bánh trừ đi tổng giá mua các hộp đã đặt. Những chiếc bánh không được đóng hộp sẽ được nhân viên IOI thưởng thức và không ảnh hưởng đến lợi nhuận.

Yêu cầu

Cho giá của từng chiếc bánh, sức chứa và giá của từng loại hộp, hãy tính lợi nhuận lớn nhất mà công ty IOI có thể thu được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(M, N\) cách nhau bởi một dấu cách, cho biết có \(M\) chiếc bánh và \(N\) loại hộp.
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa số nguyên \(P_i\), là giá tính bằng yên của chiếc bánh thứ \(i\), với \(1 \le i \le M\).
• Dòng thứ \(j\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(C_j, E_j\) cách nhau bởi một dấu cách. Hộp thứ \(j\) đựng được tối đa \(C_j\) chiếc bánh và có giá \(E_j\) yên, với \(1 \le j \le N\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: lợi nhuận lớn nhất công ty IOI có thể thu được, tính bằng yên.

Ràng buộc

• \(1 \le M \le 10\,000\).
• \(1 \le N \le 500\).
• \(1 \le P_i \le 10\,000\) với \(1 \le i \le M\).
• \(1 \le C_j \le 10\,000\) với \(1 \le j \le N\).
• \(1 \le E_j \le 10\,000\) với \(1 \le j \le N\).

Phân nhóm

• Nhóm 1 (25 điểm): \(N \le 10\).
• Nhóm 2 (35 điểm): \(C_j \le 10\) với mọi \(1 \le j \le N\).
• Nhóm 3 (40 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3
180
160
170
190
2 100
3 120
4 250

480

2 2
1000
2000
1 6666
1 7777

0

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

450