409856: GYM103810 E Экспедиция

В некоторых точках длинной прямой дороги, идущей через пустыню, расположены посадочные площадки. Известны расстояния от начала дороги до каждой из площадок. Несколько экспедиций хотят добраться до разных точек на дороге. Для этого каждая экспедиция должна сначала высадиться на одной из площадок (не обязательно ближайшей к нужной точке), затратив на это определенное количество топлива для вертолета, а затем проехать от площадки до нужной точки по дороге, затратив дополнительное топливо на каждую единицу пути. Напишите программу, которая рассчитает для каждой экспедиции, какое минимальное количество топлива необходимо для доставки экспедиции в заданную точку.

В первой строке ввода содержатся три целых числа: количество площадок $$$N$$$ $$$(1 \le N \le 10^5)$$$, количество экспедиций $$$M$$$ $$$(1 \le M \le 10^5)$$$ и затраты топлива на проезд одной единицы дороги $$$C$$$ $$$(1 \le C \le 10^9)$$$. Далее следует N строк, содержащих по два целых числа: расстояние от начала дороги до $$$i$$$-й площадки $$$A_i$$$ $$$(0 \le Ai \le 10^9)$$$ и затраты топлива для доставки экспедиции на $$$i$$$-ю площадку $$$B_i$$$ $$$(1 \le Bi \le 10^9)$$$. Все площадки расположены в разных точках дороги. Далее следует $$$M$$$ строк, содержащих одно целое числа: расстояние от начала дороги до цели $$$j$$$-й экспедиции $$$D_j$$$ $$$(0 \le D_j \le 10^9)$$$.

Для каждой экспедиции вывести одно целое число на отдельной строке – минимальное количество топлива для доставки экспедиции в заданную точку.

3 2 1
200 300
300 100
100 250
150
110

250
260

Пояснение к примеру: первая экспедиция высаживается на второй площадке (на расстоянии 300 от начала дороги), затратив 100 единиц топлива, а затем проезжает до точки 150, затратив еще 150 единиц топлива. Вторая экспедиция высаживается на третьей площадке (на расстоянии 100 от начала дороги), затратив 250 единиц топлива, а затем проезжает до точки 110, затратив еще 10 единиц топлива.