_minhduc biết rằng muốn tán được người yêu cũ của shiba thì trước tiên bản thân phải giàu trước đã. Nhờ sự dẻo mồm nịnh hót của mình nên _minhduc trở thành giám đốc của một công ti giàu nhất Việt Nam ~trước khi shiba thành lập nên một công ti lớn hơn cả công ti này...~. Từ đây, có một vấn đề "nho nhỏ" lại được sinh ra...

Trong mùa hè, trường đại học Flower_On_Stone đã gửi \(M\) sinh viên, được đánh số từ \(1\) đến \(M\), tham gia các cuộc nghiên cứu với các địa điểm khác nhau. Tất cả các địa điểm đều gần một con đường, bắt đầu từ trường Flower_On_Stone, và sinh viên thứ \(i\) đang ở địa điểm cách Flower_On_Stone \(x_i\) km (theo hướng từ trái qua phải). Tất cả các \(x_i\) đều là số nguyên không âm và chúng ta có \(x_1 \le x_2 \le … \le x_{M-1} \le x_M\).

Do công việc nghiên cứu khoa học sôi nổi trong mùa hè, tất cả các sinh viên đã tiêu hết tiền của họ và họ cần Flower_On_Stone cung cấp thêm tiền để có thể trở về trường. Mỗi sinh viên sẽ về trường bằng con đường sinh viên đó đi từ trường đến địa điểm họ tham gia nghiên cứu (có nghĩa là khoảng cách từ địa điểm họ đang tham gia về trường cũng là \(x_i\), nhưng chỉ được đi từ phải qua trái). Sinh viên thứ \(i\) sẽ cần \(v_i\) VND cho mỗi km để chi trả cho thức ăn và các nhu cầu khác. Ngoài ra, có các chuyến xe bus ở \(N\) địa điểm mà các sinh viên có thể thuê. Một chiếc xe bus ở địa điểm cách \(y_j\) km từ Flower_On_Stone sẽ có chi phí là \(c_j\) VND và nó có thể chở các sinh viên trở lại trường (tất nhiên là các xe bus sẽ đi hướng bên trái để giúp các sinh viên về đến trường). Mỗi lần thuê một chiếc xe thì chiếc xe đó chở được nhiều người mà chỉ cần trả với giá \(c_j\) một lần(*). Các chiếc xe bus di chuyển trực tiếp đến Flower_On_Stone mà không có các trạm dừng trung gian để người khác lên xe. Trường đại học đã đặt điều kiện rằng mỗi sinh viên bắt buộc phải trở lại Flower_On_Stone bằng xe bus để đảm bảo rằng mỗi sinh viên sẽ xuống ở trạm của trường đại học và sẽ đến trường để giao các tài liệu đã được thu thập trong cuộc nghiên cứu.

Ban đầu, _minhduc chỉ cần tính toán số tiền tối thiểu cần thiết để tất cả sinh viên có thể trở về trường để còn viết chi phiếu phát tiền cho học sinh. Tuy nhiên, sếp của anh ấy lại yêu cầu biết thêm số tiền tối thiểu cần trả để trả về lần lượt là chỉ cho sinh viên đầu tiên (đang ở gần trường nhất, chỉ cho \(2\) sinh viên đầu tiên (có số thứ tự là \(1\) và \(2\)), và cứ như thế cho đến tất cả các sinh viên. Do yêu cầu thêm độ khó cho công việc, sau khi hoàn thành nhiệm vụ này, _minhduc sẽ được một kỉ nghì dài hạn. Dù chiếc Macbook M2 Pro đã sửa xong từ đời nào, tuy nhiên sau vài năm nó đã cũ và không thể sử dụng được. Bạn hãy giúp _minhduc nhé ~để cậu ấy còn lên kế hoạch cưa đổ "người yêu cũ" của shiba nào :Đ~.

Yêu cầu: Bạn hãy viết một chương trình để giúp _minhduc tính toán tổng số tiền tối thiểu cần thiết để tất cả sinh viên có thể trở về Flower_On_Stone. Hơn nữa, ban quản lý đại học muốn biết số tiền tối thiểu cần trả để trả về lần lượt là chỉ cho sinh viên đầu tiên (đang ở gần nhất), chỉ cho \(2\) sinh viên đầu tiên (có số thứ tự là \(1\) và \(2\)), và cứ như thế đến khi in ra tất cả \(M\) sinh viên.

Input

• Dòng đầu tiên chứa số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó \((1 \le \phi \le 5)\).

• Dòng tiếp theo chứa số nguyên dương \(N\) – số lượng địa điểm có xe bus để cho thuê. \((1 \le N \le 10^5)\).

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên không âm lần lượt là \(y_j\) và \(c_j\) - lần lượt là khoảng cách từ Flower_On_Stone đến địa điểm tương ứng nơi có thể thuê xe bus, và chi phí thuê xe bus tại địa điểm đó \((0 \le y_j \le 2^{30}, 1 \le c_j \le 2^{40})\).

• Dòng tiếp theo chứa số nguyên dương \(M\) - số sinh viên tham gia vào cuộc nghiên cứu \((1 \le M \le 10^5)\).

• \(M\) dòng cuối cùng, mỗi dòng chứa hai số nguyên không âm \(x_i\) và \(v_i\) - lần lượt là khoảng cách từ Flower_On_Stone đến địa điểm nơi sinh viên tương ứng được gửi đi vào địa điểm đó, và số tiền mà sinh viên đó cần để đi bộ mỗi km \((0 \le x_i \le 2^{30}, 1 \le v_i \le 2^{30})\).

• Bộ dữ liệu luôn đảm bảo rằng \(x_i \le x_{i+1}\) với mọi \(1 \le i < M\) và \(y_j \le y_{j+1}\) với mọi \(1 \le j < N\) và đáp án không vượt quá \(10^{18}\).

• Bộ dữ liệu vào luôn đảm bảo rằng sẽ có ít nhất một chiếc xe bus đủ điều kiện để chở tất cả các sinh viên về trường.

Output

• Gồm \(M\) dòng. Dòng thứ \(i\) \((1 \le i \le M)\) in ra số tiền tối thiểu để \(i\) sinh viên đầu tiên có thể về.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\), \(M \le 6\).

• Subtask \(2\) (\(20\%\) số điểm): Dữ kiện đề bài khác với (*) rằng tất cả các sinh viên đi cùng một chiếc xe bus bất kì mỗi người đều trả tiền cho chiếc xe đó và tất cả các giá trị \(v_i\) đều bằng nhau.

• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 14\), \(M \le 100\).

• Subtask \(4\) (\(25\%\) số điểm): Có \(N \le 1000\), \(M \le 100\).

• Subtask \(5\) (\(15\%\) số điểm): Có \(N \le 2 \times 10^4\), \(M \le 1000\).

Example

1
3
6 5
7 10
28 12
3
7 1
8 9
29 11

6
19
42

2
3
6 5
7 10
28 12
3
7 1
8 1
29 1

6
13
26