Cô giáo chủ nhiệm cần tính toán kế hoạch chi tiêu cho ~M~ học sinh trở về trường sau một chuyến tham quan dã ngoại. Các học sinh được đánh số từ 1 đến ~M~. Trường và các địa điểm tham quan đều nằm trên một trục đường giao thông. Hiện tại, tính từ trường thì học sinh thứ ~i~ tham quan tại địa điểm cách trường ~x_i~ km. Tất cả các ~x_i~ đều là số nguyên không âm và ~x_1 \le x_2 \le \ldots \le x_{M-1} \le x_M~. Mỗi học sinh phải đi thẳng về trường, họ có thể đi bộ hoặc đi bằng xe buýt. Khi đi bộ thì học sinh thứ ~i~ cần ~v_i~ đồng cho mỗi km để uống nước hoặc dùng cho các chi phí cần thiết khác.

Có ~N~ xe buýt, được đánh số từ 1 đến ~N~. Xe thứ ~j~ chờ khách tại địa điểm cách trường ~y_j~ km và khi được thuê để về trường cần phải trả ~c_j~ đồng. Tất cả các ~y_j~ đều là số nguyên không âm và ~y_1 \le y_2 \le \ldots \le y_{N-1} \le y_N~. Có thể có nhiều học sinh cùng lên một chuyến xe nếu họ đang ở tại địa điểm chờ khách của xe đó. Mỗi chuyến xe được thuê, dù chỉ có một người đi hay nhiều người cùng đi thì tiền thuê xe cũng không thay đổi. Mỗi xe được thuê sẽ chạy thẳng từ địa điểm chờ về trường, không dừng lại đón các học sinh khác tại bất kỳ một địa điểm nào trên đường.

(Vì phải đi thẳng về trường nên một học sinh ở vị trí ~x_i~ chỉ có thể đi bộ tới xe buýt có ~y_j \le x_i~ rồi đi xe đó về trường, chi phí ~(x_i - y_j) \cdot v_i + c_j~; hoặc đi bộ toàn bộ quãng đường về trường, chi phí ~x_i \cdot v_i~.)

Hãy giúp cô giáo tính toán tổng số tiền ít nhất để đưa học sinh về trường, cụ thể hơn giúp cô tính tổng số tiền ít nhất để đưa một học sinh đầu tiên, hai học sinh đầu tiên, ..., cuối cùng là ~M~ học sinh về trường.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \ge 1~) là số xe buýt;
• ~N~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên dương ~y_j~, ~c_j~ cách nhau dấu cách;
• Dòng tiếp theo chứa số nguyên dương ~M~ (~M \ge 1~) là số học sinh;
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~x_i~, ~v_i~ cách nhau dấu cách.

Giới hạn: ~0 \le x_i, y_j \le 2^{30}~; ~x_i \le x_{i+1}~ với mọi ~1 \le i < M~; ~y_j \le y_{j+1}~ với mọi ~1 \le j < N~; ~1 \le v_i \le 2^{30}~, ~1 \le c_j \le 2^{40}~.

Kết quả

Gồm một dòng ghi ~M~ số nguyên dương, các số cách nhau dấu cách, số thứ ~k~ là tổng số tiền ít nhất để đưa ~k~ học sinh đầu tiên về trường.

Ví dụ

PLAN.INP

6
1 3
2 10
3 100
4 100
5 15
6 10
3
2 5
4 9
8 3

PLAN.OUT

8 28 44

Giải thích: Kế hoạch đi và chi phí nhỏ nhất:

• Với học sinh đầu tiên, học sinh 1 đi bộ đến địa điểm chờ của xe số hiệu 1, sau đó đi xe số hiệu 1 về trường, chi phí: ~(2 - 1) \times 5 + 3 = 8~.
• Với hai học sinh đầu tiên, học sinh 2 đi bộ đến địa điểm xe số hiệu 2, sau đó hai người cùng đi trên một chuyến xe số hiệu 2 về trường, chi phí: ~(2 - 2) \times 5 + (4 - 2) \times 9 + 10 = 28~.
• Với ba học sinh, học sinh 1 và 2 đi như trên với chi phí 28. Còn học sinh 3 đi bộ đến địa điểm xe số hiệu 6, sau đó đi xe số hiệu 6 về trường, chi phí: ~(8 - 6) \times 3 + 10 = 16~. Chi phí cả ba học sinh là: ~28 + 16 = 44~.

Giới hạn

• Subtask 1 (10% số test): ~N \le 10~, ~M \le 6~;
• Subtask 2 (20% số test): ~N \le 14~, ~M \le 10^2~;
• Subtask 3 (40% số test): ~N \le 10^3~, ~M \le 10^2~;
• Subtask 4 (30% số test): ~N \le 2 \times 10^4~, ~M \le 10^3~.