Sau một thời gian, các bác nông dân thấy các cây phát triển không đều nhau. Các bác tiến hành thay đổi phương pháp chăm cây, các cây được đánh số thứ tự từ 1 đến n. Nghiên cứu cho thấy để cây phát triển tốt thì cây thứ i cần một lượng đạm tối thiểu là ai cho một đợt chăm. Một đợt chăm, mỗi cây chỉ được bón một lần với khối lượng 1 kg của cùng một loại phân bón. Công ty cung cấp phân bón đưa ra một bảng danh sách gồm m loại phân bón. Trong 1kg thì loại thứ j có lượng đạm là bj và giá tiền là cj (mỗi loại phân bón đều không hạn chế số lượng). Yêu cầu: Em hãy giúp các bác nông dân tính số tiền ít nhất cần mua n kg phân bón để chăm cho tất cả các cây và thỏa mãn yêu cầu lượng đạm tối thiểu của từng cây trong đợt này. Biết rằng công ty luôn cung cấp đủ số lượng và đáp ứng được yêu cầu lượng đạm của các cây. Dữ liệu vào: • Dòng 1: Số nguyên nnn là số lượng cây (1 ≤ n ≤ 100000). • Dòng 2: Chứa n số nguyên dương ai, mỗi số thể hiện lượng đạm tối thiểu cần cho cây thứ i (1 ≤ ai ≤ 100000). • Dòng 3: Số nguyên m, là số loại phân bón có sẵn (1 ≤ m ≤ 100000). • m dòng tiếp theo, mỗi dòng chứa hai số nguyên bi và ci tương ứng là lượng đạm chứa trong 1 kg phân bón loại thứ j và giá tiền của 1 kg phân bón đó (1 ≤ bi , ci ≤ 100000). Dữ liệu ra: • Một số nguyên duy nhất là tổng số tiền ít nhất cần chi để mua đủ phân bón cho tất cả các cây. Ví dụ: Input 3 2 1 3 4 1 10 1 5 10 7 2 3 Output 13 Giải thích Mua 2kg với giá 3 có lượng đạm là 2 để bón cho cây thứ nhất và cây thứ hai, mua 1kg với giá là 7 có lượng đạm là 10 để bón cho cây thứ ba. Vậy tổng tiền hết là 13.