expedition

Deni is working at the accounting department of the Shumen university and was given the following task: during the summer the university has sent M students, numbered from 1 to M, on ethnographic expeditions in different places. Due to the circumstances, all places are near a road, that starts from Shumen, and student with number i is located in place that is $x_i$ kilometers away from Shumen. All $x_i$ are non-negative integers and we have that $x_1 ≤ x_2 ≤ … ≤ x_{M-1} ≤ x_M$.

Because of the intense science work during the summer 😉 the students have spent all their money and have made a request to the university for more money so that they can return to Shumen. Each student will use the road, leading to Shumen, in the direction from his place to Shumen. He can walk and use a bus from some of the places near Shumen. When he walks, student with number i needs $v_i$ levs for each kilometer for food and other needs. Also, there are buses in N places which the students can rent. A bus in a place, which is $y_j$ kilometers away from Shumen, costs $c_j$ levs to be rent and it can transport the students, that are using it, to return to Shumen. If a bus is rent once, then it can be used by several students, which have gathered at this place, paying the cost $c_j$ only once. The buses travel directly to Shumen without intermediate stops for other people to get in. The university has set the condition that every student should return to Shumen with a bus so it will be certain that every student will get off at the stop of the university and will go the university to give the materials that have been collected during the expedition.

Task

Write a program to help Deni calculate the minimum total amount of money which is needed so that all students can return to Shumen. Furthermore – the university management wants to know what are the minimal amounts for the return of only the first student (who is located in the nearest place), only the first 2 students (with numbers 1 and 2) and so on, lastly of all the M students.

Input data

The first line of the standard input contains the positive integer N – the number of places that have buses for rent.

The following N lines contain two non-negative integers, separated by a space, and the j-th of them contains:

• $y_j$ – the distance from Shumen for the corresponding place in which a bus can be rent;
• $c_j$ – the cost for renting a bus in that place.

The next line contains the positive integer M – the number of students which are sent on ethnographic expeditions.

The last M lines contain two non-negative integers, separated by a space, and the i-th of them contains:

• $x_i$ – the distance from Shumen for the place where the corresponding student was sent on ethnographic expedition;
• $v_i$ – the amount of money that student needs for walking one kilometer.

Output data

On the only line of the standard output print M numbers, separated by spaces – the minimum amounts of money which are needed for the return of only the first student (who is located in the nearest place), only the first 2 students (with numbers 1 and 2) and so on, lastly of all the M students.

Constraints and clarifications

• $1 ≤ N, M ≤ 10^5$
• $0 ≤ x_i, y_j ≤ 2^{30}$ and $x_i ≤ x_{i+1}$for all 1 ≤ i < N; $y_j ≤ y_{j+1}$ for all 1 ≤ j < M
• $1 ≤ v_i ≤ 2^{30}$
• $1 ≤ c_j ≤ 2^{40}$

Subtask 1 (11 points)

• N ≤ 10
• M ≤ 6

Subtask 2 (26 points)

• $N ≤ 10^5$
• $M ≤ 10^5$
• Every student has to pay for renting a bus even if several students travel together! Also, all $v_i$ are equal.

Subtask 3 (17 points)

• N ≤ 14
• M ≤ 100

Subtask 4 (23 points)

• N ≤ 1 000
• M ≤ 100

Subtask 5 (23 points)

• $N ≤ 2 \cdot 10^4$
• M ≤ 1000

Example 1

stdin

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

stdout

8 28 44

Explanation

Here the answers are for the original statement. The optimal solutions are the following:

• for the first student – student 1 goes to place 1 and his return costs $(2-1) \cdot 5+3=8$
• for the first 2 students – student 1 and 2 go to place 2 and their return costs $(2-2) \cdot 5+(4-2) \cdot 9+10=28$
• for all students – students 1 and 2 again go to place 2 and their return costs 28 and student 3 goes to place 6 and his return costs $(8-6) \cdot 3+10=16$ and so the total amount is 44

Example 2

stdin

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

stdout

10 34 58

Explanation

Here the answers are for the condition of the second subtask. The optimal solutions are the following:

• for the first student – student 1 goes to place 2 and his return costs $(2-2) \cdot 7+10=10$
• for the first 2 students – students 1 and 2 go to place 2 and their return costs $(2-2) \cdot 7+10+(4-2) \cdot 7+10=34$
• for all students – students 1 and 2 again go to place 2 and their return costs 34 and student 3 goes to place 6 and his return costs $(8-6) \cdot 7+10=24$ and so the total amount is 58