Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В некоторых точках длинной прямой дороги, идущей через пустыню,
расположены посадочные площадки.
Известны расстояния от начала дороги до каждой из площадок.
Несколько экспедиций хотят добраться до разных точек на дороге.
Для этого каждая экспедиция должна сначала высадиться на одной из площадок
(не обязательно ближайшей к нужной точке), затратив на это определенное количество топлива для вертолета,
а затем проехать от площадки до нужной точки по дороге, затратив дополнительное топливо на каждую единицу пути.
Напишите программу, которая рассчитает для каждой экспедиции, какое минимальное количество топливо необходимо для
доставки экспедиции в заданную точку.
В первой строке ввода содержатся три целых числа: количество площадок `N` (`1 <= N <= 10^5`),
количество экспедиций `M` (`1 <= M <= 10^5`) и затраты топлива на проезд одной единицы дороги `C` (`1 <= C <= 10^9`).
Далее следует `N` строк, содержащих по два целых числа: расстояние от начала дороги до `i`-й
площадки `A_i` (`0 <= A_i <= 10^9`) и затраты топлива для доставки экспедиции на `i`-ю площадку
`B_i` (`1 <= B_i <= 10^9`). Все площадки расположены в разных точках дороги.
Далее следует `M` строк, содержащих одно целое числа: расстояние от начала дороги до цели `j`-й экспедиции `D_j` (`0 <= D_j <= 10^9`).
Для каждой экспедиции вывести одно целое число на отдельной строке -- минимальное количество топлива для доставки экспедиции в заданную точку.
```sample Пример ввода
3 2 1
200 300
300 100
100 250
150
110
```
```sample Пример вывода
250
260
```
Пояснение к примеру: первая экспедиция высаживается на второй площадке (на расстоянии 300 от начала дороги),
затратив 100 единиц топлива, а затем проезжает до точки 150, затратив еще 150 единиц топлива.
Вторая экспедиция высаживается на третьей площадке (на расстоянии 100 от начала дороги), затратив 250 единиц топлива, а
затем проезжает до точки 110, затратив еще 10 единиц топлива.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (30 баллов)||
`N = 1`, `M = 1`
В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 2 (40 баллов)||
`1 < N <= 1000`, `1 < M <= 1000`
Необходимые подзадачи: 1.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
`1000 < N <= 100000`, `1000 < M <= 100000`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Начало
Рабочее место участника
Бинарный поиск