Cô giáo cần tính toán kế hoạch đưa 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 ≤ x_2 ≤ x_{M-1} ≤ 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 để 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 ≤ y_2 ≤ ...≤ y_{N-1} ≤ 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.

Yêu cầu: 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 vào: gồm:

• Dòng đầu tiên chứa số nguyên dương N (N ≥ 1);
• 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 ≥ 1);
• 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. (~0 ≤ x_i , y_j ≤ 2^{30}~; ~x_i ≤ x_{i+1}~, với mọi i: 1 ≤ i < N; ~y_j ≤ y_{j+1}~, với mọi j: 1 ≤ j < M; ~1 ≤ v_i ≤ 2^{30}~, ~1 ≤ c_j ≤ 2^{40}~)

Kết quả: ghi ra 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.

Ràng buộc:

• 10% số tests tương ứng với 10% số điểm của bài có: N ≤ 10, M ≤ 6;
• 20% số tests khác tương ứng với 20% số điểm của bài có: N ≤ 14, M ≤ ~10^2~
• 40% số tests khác tương ứng với 40% số điểm của bài có: N ≤ ~10^3~, M ≤ ~10^2~
• 30% số tests còn lại tương ứng với 30% số điểm của bài có: N ≤ ~2 × 10^4~, M ≤ ~10^3~.

Ví dụ:

Input

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

Output

8 28 44

Giải thích ví dụ:

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) x 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) x 5 + (4-2) x 9 + 10 = 28.
• Với ba học sinh, học sinh 2 đi bộ đến địa điểm xe số hiệu 2, sau đó cả hai người đi xe số hiệu 2 về trường, 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) x 3 + 10 = 16. Chi phí cả ba học sinh là: 28 +16 = 44.

Nguồn