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}\) kilometers. Tất cả các \(x_{i}\) đều là số nguyên không âm và \(x_{1} \leq x_{2} \leq \cdots \leq x_{M - 1} \leq x_{M}\). Mỗi học sinh phải đi thẳng về trường, họ có thể gọi xe taxi hoặc đi bằng xe buýt. Khi đi taxi thì học sinh thứ \(i\) cần \(v_{i}\) đồng để đi được 1 kilometers.

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}\) kilometers 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} \leq y_{2} \leq \cdots \leq y_{N - 1} \leq 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:

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \geq 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 \geq 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 \leq x_{i},\ y_{j} \leq 2^{30};x_{i} \leq x_{i + 1},\forall i:1 \leq i < N;y_{j} \leq y_{j + 1},\forall j:1 \leq j < M;1 \leq v_{i} \leq 2^{30},\ \ 1 \leq c_{j} \leq 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ụ

Ràng buộc:

• Subtask 1: 10% số test đầu tiên có \(N \leq 10,M \leq 6;\)

• Subtask 2: 20% số test tiếp theo có \(N \leq 14,M \leq 10^{2};\)

• Subtask 3: 40% số test tiếp theo có \(N \leq 10^{3},M \leq 10^{2}\);

• Subtask 4: 30% số test cuối cùng có \(N \leq 2 \times 10^{4},M \leq 10^{3}.\)