План – 1
Задачу добавил: alef
Успешно сдано решений: 49
Конечно, снегом оказались завалены не только крыши, но и дороги, и тротуары...
Начальник дорожной службы решил, что сначала должны быть расчищены самые широкие дороги, и хочет оценить объем работ.
У него имеется список N дорог, в котором указана их длина и ширина. На очистку 1 кв. единицы длины дороги по нормативам требуется T единиц времени.
Однако начальник еще не определился, какова должна быть минимальная ширина дороги, чтобы отнести ее к "самым широким". Поэтому он хотел бы получить расчет для нескольких вариантов.
Ваша задача - помочь ему в этом.
Формат входного файла input.txt
Первая строка – целое число V (1 <= V <= 100) – количество вариантов минимальной ширины дорог, для которых начальник дорожной службы хотел бы получить расчет.
Вторая строка – V целых чисел W1, W2, ..., WV (1 <= Wj <= 1000, j = 1, 2, ..., V) через пробел. Число Wj обозначает минимальную ширину дороги, которая в варианте #j будет отнесена к "самым широким".
Третья строка – целые числа N и T через пробел (1 <= N <= 5000000, 1 <= T <= 1000), N - количество дорог в списке, T – время, которое требуется, чтобы очистить единицу площади ( = единицу длины в квадрате) дороги.
Каждая из следующих N строк содержит по два целых числа D и L (1 <= D <= 1000, 1 <= L <= 100000) через пробел - ширину и длину очередной дороги.
Формат выходного файла output.txt
Первая строка - V целых чисел S1, S2, ..., Sj, ..., SV через пробел – количество единиц времени, которое потребуется, чтобы почистить все дороги шириной не менее W1, W2, ..., Wj, ... , WV соответственно.
Пример входного файла
3
1 5 10
10 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
Пример выходного файла
55 45 10