In certain points along a long straight road, landing pads are located. The distances from the start of the road to each of the landing pads are known. Several expeditions want to reach specific points on the road, starting from its beginning, using a helicopter. For this purpose, each expedition must land at one of the designated landing pads at least once (not necessarily the closest one to the desired point), using a specific amount of helicopter fuel. It is important to note that if, for example, there is only one landing pad located exactly at the beginning of the road, the helicopter must land on that pad after takeoff. After landing at one of the landing pads, the expedition must proceed on foot (forward or backward if the desired point does not coincide with the landing pad) to the desired point along the road. During this movement, a certain amount of fuel is consumed for each unit of distance traveled on the road. Write a program called "expedition" that finds, for each expedition, the minimum amount of fuel required to deliver the expedition to the specified point.
INPUT
The input on the first line of the standard input consists of three integers: N, M, and C - the number of landing pads, the number of expeditions, and the fuel consumption for walking one unit length on the road. The following N lines each contain two integers: A_i - the distance from the start of the road to the i-th landing pad, and B_i - the fuel consumption required to deliver the expedition to the i-th landing pad. All landing pads are located at different points on the road. The next M lines contain a single integer each: D_j - the distance from the start of the road to the destination of the j-th expedition.
OUTPUT
For each flight, the program should output, on a separate line of the standard output, a single integer representing the minimum cost for transporting the expedition.
RESTRICTION
1 <= N <= 10**5 1 <= M <= 10**5 1 <= C <= 10**9 0 <= Ai <= 10**9 0 <= Bi <= 10**9 0 <= Dj <= 10**9
my016658 2년 전
EXPEDITION
In certain points along a long straight road, landing pads are located. The distances from the start of the road to each of the landing pads are known. Several expeditions want to reach specific points on the road, starting from its beginning, using a helicopter. For this purpose, each expedition must land at one of the designated landing pads at least once (not necessarily the closest one to the desired point), using a specific amount of helicopter fuel. It is important to note that if, for example, there is only one landing pad located exactly at the beginning of the road, the helicopter must land on that pad after takeoff. After landing at one of the landing pads, the expedition must proceed on foot (forward or backward if the desired point does not coincide with the landing pad) to the desired point along the road. During this movement, a certain amount of fuel is consumed for each unit of distance traveled on the road.
Write a program called "expedition" that finds, for each expedition, the minimum amount of fuel required to deliver the expedition to the specified point.
INPUT
The input on the first line of the standard input consists of three integers: N, M, and C - the number of landing pads, the number of expeditions, and the fuel consumption for walking one unit length on the road.
The following N lines each contain two integers: A_i - the distance from the start of the road to the i-th landing pad, and B_i - the fuel consumption required to deliver the expedition to the i-th landing pad.
All landing pads are located at different points on the road.
The next M lines contain a single integer each: D_j - the distance from the start of the road to the destination of the j-th expedition.
OUTPUT
For each flight, the program should output, on a separate line of the standard output, a single integer representing the minimum cost for transporting the expedition.
RESTRICTION
1 <= N <= 10**5
1 <= M <= 10**5
1 <= C <= 10**9
0 <= Ai <= 10**9
0 <= Bi <= 10**9
0 <= Dj <= 10**9